[贪心] poj 2376 Cleaning Shifts

题意：

给n个线段，问你覆盖满[1,T]内的每个点，最少需要多少条线段。

思路：

贪心，按照x坐标升序，，y坐标降序排。

默认先放入第一条。

然后根据从属关系继续放线段。

注意的一点是 [1,2]和[3,4]就可以覆盖满[1,4]了。

然后注意因为默认放入了第一条，所第一条的状态要特判。

包括 第一条如果是[1,T]的话 输出1.

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"using namespace std;struct node{int x,y;}p[26000];int cmp(node a,node b){if(a.x==b.x){if(a.y>b.y) return 1;return 0;}if(a.x<b.x) return 1;return 0;}int main(){int n,m;while(scanf("%d%d",&n,&m)!=-1){for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);sort(p,p+n,cmp);if(p[0].x!=1){puts("-1");continue;}int xx=0;int yy=p[0].y;int ans=1;for(int i=1;i<n;i++){if(p[i].y<yy) continue;if(yy>=m) break;if(p[i].x>yy+1){ans=-1;break;}if(p[i].x>xx+1){ans++;xx=yy;yy=p[i].y;}else{yy=p[i].y;}}if(yy<m) ans=-1;printf("%d\n",ans);}return 0;}

真正的爱，应该超越生命的长度心灵的宽度灵魂的深度