Question

杭电oj :2037今年暑假不ac 在自己电脑上输出都是对的，提交后就是WA。 帮我看一下算法哪里错了，谢谢。

#include<iostream>
int main()
{
using namespace std;
int n;
while(cin>>n&&n!=0)
{
int a[102][2],t=n;
int j,i;
for(j=0;j<t;j++)
{
cin>>a[j][0]>>a[j][1];
}
for(j=0;j<t-1;j++)
for(i=j;i<t;i++)
{
if(a[j][1]>a[i][1])
{
int p=a[j][1];
a[j][1]=a[i][1];
a[i][1]=p;
}
}
int x=0,con=0;
for(i=0;i<t;i++)
{
if(a[i][0]>=x)
{
con++;
x=a[i][1];
}
}
cout<<con<<endl;
}
return 0;
}

Answer 1

这道题应该用贪心的思想来做，每个节目写成一个结构体，将每个节目按照结束的时间升序排序。这个用sort很容易就能办到的，如果不知道怎么用sort对结构体排序，建议先看看sort的使用方法。接下来就是用贪心的思想枚举，枚举出每一个节目作为第一个节目看最多能看多少个。找出其中的最大值就是最多能看的节目数目了。觉得你的程序和解题的思路偏离的比较大啊，看不出你对每个电视节目进行了排序（或者说你的排序写的有问题），也没看出贪心实现。建议按照上面的思路重新写一遍吧。还有搞ACM应该是有看到思路就能用代码实现的能力，而不是动不动就让人帮忙调试代码。应该锻炼一下自己debug的能力。
样例代码，仅供参考：
#include <iostream>#include <algorithm>
using namespace std;

struct channel{
int start;
int end;
};

int Max(int a, int b);bool Cmp(channel a, channel b);
int main(void){
int i;
int j;
int n;
int num_chan;
int max_chan;

channel last_chan; channel chan[1005];
while ((cin>>n) && (n!=0)) {
max_chan = 0;

for (i=0; i<n; ++i) {
cin >> chan[i].start >> chan[i].end;
}

sort(chan, chan+n, Cmp);
for (i=0; i<n; ++i) {
num_chan = 1;
last_chan = chan[i];

for (j=i; j<n; ++j) {
if (chan[j].start >= last_chan.end)
{
++num_chan;
last_chan = chan[j];
}
}

max_chan = Max(max_chan, num_chan); }
cout << max_chan << endl; }
return 0;}
int Max(int a, int b){
return a > b ? a : b;
}

bool Cmp(channel a, channel b){
return a.end < b.end;
}

追问

谢谢,明白怎么回事了。我想再问一下acm的事,我刚学完C语言。数据结构，c＋＋，算法，离散学校都没上呢，之前我自学数据结构但看到中间时，就看不懂了，后来又看刘汝佳的入门经典，看了一大半，到了后面有关数据结构的地方又看不懂了，离散还没看，c＋＋也是自学的，刚学没多久，感觉还可以，但感觉搞了一段时间的acm提升并不大，现在有种不知道如何下手，怎样进行的感觉，希望您帮我指点一下，提些建议，谢谢。

追答

建议还是先看看严蔚敏的《数据结构 C语言版》，刚刚接触数据结构时可能会在学到树和图的时候有些困惑，但是不要紧，慢慢来。建议你先重头看一遍数据结构吧，估计前面你看过的部分有很多知识点都是模棱两可的。一般搞ACM都是先学C或者是C++，之后学数据结构，再往后才是算法。当然，一些非常简单的算法是要会的，比如简单的求和算法，最大公约数之类的。之后才能由浅入深。一般学校的ACM集训队可能就是会每一部分分专题训练。一般搞过ACM的程序员写出的代码的质量要更高，所以搞ACM还是很有用的。