题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1025
要用nlogn的算法，不然会超时
参见博客讲解：http://blog.csdn.net/kaitangshouljz/article/details/41074187?locationNum=7
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=500000+5;
struct Road
{int poor,rich;bool operator < (const Road& r) const {return poor<r.poor;}
}road[maxn];
int d[maxn];
int BinerySearch(int L,int R,int x){int mid;while(L<=R){mid=L+(R-L)/2;if(d[mid]<x&&d[mid+1]>=x) return mid;else if(d[mid]<x) L=mid+1;else R=mid-1;}return 0;
}
int LIS(int N){memset(d,0,sizeof(d));int len=1,p;d[1]=road[1].rich;for (int i = 2; i <= N; ++i){int n=road[i].rich;if(n>d[len]) p=++len;else p=BinerySearch(1,len,n)+1;d[p]=n;}// for (int j = 1; j <=len; ++j)// cout<<d[j]<<' ';// cout<<endl; return len;
}
int main()
{int N,kase=0;while(scanf("%d",&N)!=EOF){for (int i = 1; i <= N; ++i) scanf("%d%d",&road[i].poor,&road[i].rich);sort(road+1,road+N+1);int ans=LIS(N);printf("Case %d:\nMy king, at most %d %s can be built.\n\n",++kase,ans,ans==1?"road":"roads");}return 0;
}