HDU 1025最长递增子序列（二分法）

最长递增子序列（二分）

HDU1025

https://www.felix021.com/blog/read.php?1587
找最长递增子序列，以前一般用DP的方法找，因为理解简单，实现也很简单，但是复杂度是 O （ n 2 ） O（n^2） O（n2），对于一些数据量稍大的，就当场gg了。
学了一下二分法找一个序列的最长递增子序列。
思想：（就是把原来的序列插入到一个新的序列中）开一个B数组，B[i]表示最长递增子序列长度为i的最小尾值。然后不断的去更新这个尾值。二分查找当前数要插入的位置，复杂度可以降到 O ( n ∗ l o g ( n ) ) O(n*log(n)) O(n∗log(n))

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define LL long long
int a[N];
int b[N];
int len=0;
void in(int x)
{
    if(x>b[len])
    {
        b[len+1]=x;
        len++;
    }
    else
    {
        int l=1,r=len+1;
        int ans=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(b[mid]<x)
            {
                l=mid+1;
                ans=mid;
            }
            else
            {
                r=mid-1;
            }
        }

        b[ans+1]=x;
    }

}
int main()
{
    int n;
    int tot=1;
    while(~scanf("%d",&n))
    {
        len=0;

        int j;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&j);
            scanf("%d",&a[j]);
        }
        b[0]=a[0];
        for(int i=1; i<=n; i++)
        {
            in(a[i]);
        }
//    for(int i=1;i<=n;i++)
//    {
//        printf("%d**\n",b[i]);
//    }
        printf("Case %d:\n",tot++);
        if(len==1)
        {
            printf("My king, at most 1 road can be built.\n");
        }
        else
        {
            printf("My king, at most %d roads can be built.\n",len);
        }
        printf("\n");
    }
    return 0;
}