Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这题没这么难啊,区间贪心#include<stdio.h> #include<algorithm> #define M 25005 using namespace std; int N,T; struct node { int x; int y; }A[M]; bool cmp(node a,node b) { if(a.x != b.x) return a.x < b.x; else return a.y > b.y; } int main() { int i,j,str,end; int ans,end2; while(~scanf("%d%d",&N,&T)) { for(i=0;i<N;i++) scanf("%d%d",&A[i].x,&A[i].y); sort(A,A+N,cmp); if(A[0].x != 1) { printf("-1\n"); continue; } ans = 1; end2 = 0; end = A[0].y; for(i=1;i<N;i++) { if(A[i].x > end+1) { end = end2; ans++; } if(A[i].x <= end+1 && A[i].y >= end+1) { if(A[i].y > end2) end2 = A[i].y; if(A[i].y == T) { end = T; ans++; break; } } } if(end != T) printf("-1"); else printf("%d\n",ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator