hdu 1025（最大上升子序列的n*logn解法）

之前遇到過這個算法，但是當時沒有特別注意。

算法理解了七八分，但是還不夠徹底，先把代碼發出來，明天修改一下，附上完整的算法思路。

[cpp]
#include<stdio.h>  
#define N 500005  
int a[N],ans[N]; 
int main() 
{ 
    int n; 
    int x,y; 
    int i; 
    int count; 
    count=1; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d",&x,&y); 
            a[x]=y; 
        } 
        ans[1]=a[1]; 
        int ln; 
        ln=1; 
        for(i=2;i<=n;i++) 
        { 
            int low,up; 
            low=1; 
            up=ln; 
            while(low<=up) 
            { 
                int mid; 
                mid=(low+up)/2; 
                if(ans[mid]<a[i]) 
                    low=mid+1; 
                else 
                    up=mid-1; 
            } 
            ans[low]=a[i]; 
            if(low>ln) 
                ln++; 
        } 
        printf("Case %d:\n",count++); 
        if(ln==1) 
            printf("My king, at most 1 road can be built.\n"); 
        else 
            printf("My king, at most %d roads can be built.\n",ln); 
        printf("\n"); 
    } 
    return 0; 
} 

#include<stdio.h>
#define N 500005
int a[N],ans[N];
int main()
{
 int n;
 int x,y;
 int i;
 int count;
 count=1;
 while(scanf("%d",&n)!=EOF)
 {
  for(i=0;i<n;i++)
  {
   scanf("%d%d",&x,&y);
   a[x]=y;
  }
  ans[1]=a[1];
  int ln;
  ln=1;
  for(i=2;i<=n;i++)
  {
   int low,up;
   low=1;
   up=ln;
   while(low<=up)
   {
    int mid;
    mid=(low+up)/2;
    if(ans[mid]<a[i])
     low=mid+1;
    else
     up=mid-1;
   }
   ans[low]=a[i];
   if(low>ln)
    ln++;
  }
  printf("Case %d:\n",count++);
  if(ln==1)
   printf("My king, at most 1 road can be built.\n");
  else
   printf("My king, at most %d roads can be built.\n",ln);
  printf("\n");
 }
 return 0;
}