Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一步步的积累

Posted by lvweihua at 2017-08-09 10:45:06 on Problem 2376
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator