HDU-2037 今年暑假不AC

题面

【VJudge】 【HDU】

多组测试数据, 给你n个区间,求最多能选择多少个不相交的区间
n <= 100
端点处可以重合

总结

这题和上题一样，都是贪心题，都是区间题，不过这题的处理方式比较不一样 ：

因为是要求最多的不相交区间，所以我们取得每一个区间都应该尽可能的短且尽可能的接近。我们该如何设置贪心策略呢？

这次因为是要找一个尽可能短的区间，所以我们可以按照右端点排序，这样我们找出来的第一个符合要求的点就可以是最短的。

而这个要求是什么呢？答案很简单，就是左端点大于等于上一个节目的右端点（因为是电视节目看完后可以立刻去换台看下一个节目）。我们一个个去找，只要找到一个这样的节目，看电视总共的时长就是最短的，可以看的电视节目就可以更多。

槽点

1. (WA) 第一版程序犯了两个错误：
   1. 初始化不对，因为是多组数据，及时的初始化很重要！ans变量初始值应该为0（天经地义），而a变量的初始值就应该是0（st[0]=(0,0)表示一个节目也没看过）；
      错误：a=b=1;
      正确：a=0;b=1,ans=0;
   2. 终止条件不对：当找遍了所有的节目却发现没有一个能看时，b的值应该是n+1，所以：
      错误：if(b==n && st[b].first < st[a].second)
      正确：if(b==n+1)，干净而整洁；
2. (WA) 越改越错，因为不理解端点处可以重合，而将st[b].first < st[a].second改成了st[b].first <= st[a].second
3. (WA) 将循环条件改了回去，然后修改了a的初始值。
4. (WA) 总算是发现了自己没有重置ans的愚蠢错误！

AC代码

#include<bits/stdc++.h>
using namespace std;
inline bool cmp(pair<int,int> a,pair<int,int> b){
    return a.second==b.second?a.first<b.first:a.second<b.second;
}
pair<int,int> st[200];
int n,a,b,ans;
int main(){
    while(1){
        scanf("%d",&n);
        if(n==0)return 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a,&b);
            st[i]=make_pair(a,b);
        }
        sort(st+1,st+1+n,cmp);
        a=0;b=1,ans=0;
        while(a<=n){
            while(b<=n&&st[b].first<st[a].second)b++;
            if(b==n+1){
                break;
            }
            a=b;
            //cout<<st[a].first<<" "<<st[a].second<<endl;
            ans++;
        }
        printf("%d\n",ans);
    }
}

页面： 1 2 3