具体看 这里
题目就是要让两个序列都递增。
那么放入数组之后 下标递增的同时 值也递增
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int save[500005];
int len_min[500005];
int n;
int bin(int l,int r,int key)
{
int mid;
while(l<r)
{
mid=(l+r)>>1;
if(len_min[mid]<key)l=mid+1;
else r=mid;
}
return l;
}
int LIS()
{
int top=1;
len_min[0]=save[1];
for(int i=2;i<=n;i++)
{
int k=bin(0,top-1,save[i]);
if(len_min[k]>=save[i])len_min[k]=save[i];
else len_min[top++]=save[i];
}
return top;
}
int main()
{
int kase=1;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
save[x]=y;
}
int ans=LIS();
printf("Case %d:\n",kase++);
if(ans==1)printf("My king, at most 1 road can be built.\n\n");
else printf("My king, at most %d roads can be built.\n\n",ans);
}
return 0;
}
hdu 1025 Constructing Roads In JGShining's Kingdom （O(nlogn) 求LIC）
原文：http://blog.csdn.net/u010709592/article/details/18800009