| ||||||||||
| 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