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;
}

补充：软件开发 , C++ ,