描述
输入
输出
样例输入
3 10
1 7
3 6
6 10
样例输出
2
提示
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <math.h> #include <queue> #include <map> #include <stack> #include <utility> #define LL long long int const max_n = 25100; using namespace std; struct node{ int a,b; }num[max_n]; bool cmp(node x,node y)//排序函数 { if(x.a==y.a)return x.b>y.b; else return x.a<y.a; } int main() { int n,t; scanf("%d %d",&n,&t); for(int i=0;i<n;i++) { scanf("%d %d",&num[i].a,&num[i].b); } sort(num,num+n,cmp); int end=0,begin=0,sum=0;//结束时间,开始时间,计数器 bool judge=false; for(int i=0;i<n;i++) { bool tt=false;//因为后面循环体内,在给结束时间赋值后,i又加了一次,所以跳出循环的i比实际牛的小标大一,在后面进行-1处理 while(num[i].a<=begin+1&&i<n)//判断是否覆盖到了所有的时间段,如果中间出现时间断了的情况,则end值不会更新,导致begin值不会更新,每一个后来的牛的开始时间都将大于begin时间,这样在for循环内的if(begin>=t)不会执行,从而得出不能搬办到的结果。 { tt=true; end=max(end,num[i].b); i++; } begin=end; sum++; if(tt)i--; if(begin>=t){ judge=true; break; } } if(judge)printf("%d\n",sum);//只有工作时间覆盖所有时间段,且最后一头牛的结束时间大于总时间t时,输出使用的牛的数量 else printf("-1\n"); return 0; }
原文:https://www.cnblogs.com/whocarethat/p/11031355.html