首页 > 代码库 > poj 2376

poj 2376

唉,开始以为这是一个简单的贪心,后来发现并不简单,于是写了写,输出超限,怎么改都是输出超限,于是去看了大神代码,结果还是输出超限,最后发现,忘了EOF,结果加了就对了,我马上去测试一下自己的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=25000+10;
typedef pair<int,int> pp;
pp a[maxn];
int n,t;
int ans;
bool cmp(pp p,pp q)
{   if(p.first==q.first) return q.second<p.second;
    return p.first<q.first;//时间大区间套小区间
}
int solve()
{
    int num=0;
    int end=0,idx=1;
    while(end<t)
    {
        int begin=end+1;
        for(int i=idx;i<=n;i++)
        {
            if( a[i].first<=begin )
            {
                if( a[i].second>=begin )
                    end=max(end,a[i].second);//拉到最大的结束时间
            }
            else//直到找不到符合开始时间的区间
            {
                idx=i;
                break;//存下位置,结束
            }
        }
        if(begin>end)
        {
            return -1;//上面的for找不到符合的情况,无法衔接
        }
        else
        {
            num++;//上面的牛找到,抬走,找下一个

        }
    }
    return num;
}
int main()
{
    while(~scanf("%d%d",&n,&t))
    {
        ans=0;
        for(int i=1; i<=n; i++)
            scanf("%d%d",&a[i].first,&a[i].second);
        sort(a+1,a+n+1,cmp);
       printf("%d\n",solve());
    }
    return 0;
}

 

poj 2376