1025.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct road{
    int s;
    int t;
};
bool cmp(road a,road b){
    return a.s<b.s;
}
void main()
{
    int n,i,co,k=1;
    road *a;
    int *max;
    while(cin>>n){
        if(n==0){
            printf("Case %d:\nMy king, at most 0 road can be built.\n",k++);
            continue;
        }
        a=new road[n+5];
        max=new int[n+5];
        for(i=0;i<n;i++)
            scanf("%d%d",&a[i].s,&a[i].t);
        sort(a,a+n,cmp);
        int len=1;
        max[0]=-1;
        max[1]=a[0].t;
        for(i=1;i<n;i++){
            int p=0,r=len;
            while(p<=r){
                int m=(p+r)/2;
                if(max[m]>a[i].t)
                    r=m-1;
                else
                    p=m+1;
            }
            max[p]=a[i].t;
            if(p>len)
                len++;
        }
        if(len==1)
            printf("Case %d:\nMy king, at most 1 road can be built.\n",k++);
        else
            printf("Case %d:\nMy king, at most %d roads can be built.\n",k++,len);
        printf("\n");
        delete [] a;
    }
}