刷题与ZZ错误记录13

HDU-2037 今年暑假不AC

题面

【VJudge】 【HDU】

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

总结

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

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

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

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

槽点

  1. (WA) 第一版程序犯了两个错误:
    1. 初始化不对,因为是多组数据,及时的初始化很重要!ans变量初始值应该为0(天经地义),而a变量的初始值就应该是0st[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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注