竞赛讨论区 > c题值周问题 ,样例过了,代码感觉也没问题 为什么过不了
头像
深白唐
发布于 2019-07-01 14:51
+ 关注

c题值周问题 ,样例过了,代码感觉也没问题 为什么过不了

使用贪心算法,对区间进行排序,以末尾节点递增排序
#include<iostream>
#include<algorithm>
using namespace std;
struct loc{
    int first;
    int last;
};
const int MAX=1000008;
loc area[MAX];
bool com(loc a,loc b)
{
    if(a.last<b.last)
        return true;
    else if(a.last==b.last)
    {
        if(a.first<b.first)
            return true;
        else
            return false;
    }
    else
        return false;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        cin>>area[i].first>>area[i].last;
    }
    sort(area,area+m,com);
    int flag=0;
    int sum=0;
    for(int i=0;i<m;++i)
    {
        if(flag<area[i].first)
            sum+=(area[i].last-area[i].first+1);
        else
            sum+=(area[i].last-flag);
        flag=area[i].last;
    }
    cout<<n+1-sum<<endl;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐