首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。