题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1025
解题报告：先把输入按照r从小到大的顺序排个序，然后就转化成了求p的最长上升子序列问题了，当然按p排序也是一样的。但这题的n的范围是5*10^5次方，所以用n^2算法求
最长上升子序列肯定不行，下面简单介绍一下nlogn时间内求的方法：
从序列里面每次插入一个数，插入到另外一个数组里面，这个数组初始状态是空的，插入一个数时，如果这个数比这个数组里面的任何一个数都大，则直接插入到最后面，否则判断这个数跟在这个数组里面值相差最小的一个数的位置，然后这里有一个细节，就是要尽量使得这里的数很小，因为这样可以使后来可以插入后面的数的个数越多，这个仔细想想应该知道。然后最后这个数组的长度就是最长上升子序列的长度，在这题中也就是最多可以修建的路的条数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn = ;
struct node
{
int a,b;
}city[maxn];
int que[maxn]; bool cmp(node a,node b)
{
return a.a < b.a;
}
int find(int d,int len)
{
int l = ,r = len - ;
while(l < r)
{
int mid = (l + r) >> ;
if(que[mid] >= d)
r = mid;
else l = mid + ;
}
return r;
}
int main()
{
int n,kase = ;
while(scanf("%d",&n)!=EOF)
{
for(int i = ;i < n;++i)
scanf("%d%d",&city[i].a,&city[i].b);
sort(city,city+n,cmp);
que[] = city[].b; //初始化，先把1个元素放进已经有顺序的集合里面
int len = ;
for(int i = ;i < n;++i)
{
int pos = find(city[i].b,len);
if(pos == len - && que[pos] < city[i].b)
que[len++] = city[i].b;
else que[pos] = min(que[pos],city[i].b);
}
if(len > )
printf("Case %d:\nMy king, at most %d roads can be built.\n",kase++,len);
else printf("Case %d:\nMy king, at most %d road can be built.\n",kase++,len);
puts("");
}
return ;
}