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<cstdio> #include<algorithm> using namespace std; const int MAXN=25005; struct Line{ int l,r; }line[MAXN]; int N,T; int cmp(const Line &a,const Line &b){ if(a.l<b.l)return 1; else if(a.l==b.l&&a.r<b.r)return 1; else return 0; } int solve(){ sort(line,line+N,cmp); if(line[0].l!=1)return -1; //第一个就无法连接 int i=0,time=1; //time记录当前可以到达的最右侧区间 while(line[i].l==1) time=line[i++].r; int ans=1; while(time<T){ if(i>N)break; int j=i,max_r=line[i].r; while(i<N&&line[i].l<=time+1){ //学会这种区间更替方式 if(line[i].r>max_r){ j=i;max_r=line[i].r; } i++; } if(max_r<=time||line[j].l>time+1)break; //结束区间不连续或者选择区间不能覆盖 else{ ans++; time=line[j].r; } } if(time<T)return -1; else return ans; } int main(){ while(scanf("%d%d",&N,&T)!=EOF){ for(int i=0;i<N;i++) scanf("%d%d",&line[i].l,&line[i].r); printf("%d\n",solve()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator