HDU 1025 (最长上升子序列(nlogn)算法)-蒲公英云

HDU 1025 (最长上升子序列(nlogn)算法)

本题真是各种WR都遇到了。。哎。不负苦心人

题意：给一个n代表两边城市的个数，两边都有n个城市，城市编号不会重复，要求找最多能修多少路（路不能交叉）

思路：就是找最长上升子序列（用复杂度nlogn的方法做）

AC代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e5+10;
int t[maxn];
int v[maxn];
int n;
int len;
int binary_seacher(int i){
    int left=1,right=len;
    while(left<=right){   //不要忘记了这里的等号 
        int mid=(left+right)/2;
        if(v[i]>t[mid])
          left=mid+1;
        else 
           right=mid-1;
    }
    return left;
}
int main(){
    int count1=0;
    while(scanf("%d",&n)==1){
        memset(v,0,sizeof(v));
        memset(t,0,sizeof(t));
        for(int i=0;i<n;i++){
            int p,r;
            scanf("%d%d",&p,&r);
            v[p]=r;
        }
        t[1]=v[1];
        len=1;
        for(int i=2;i<=n;i++){
            if(v[i])
             if(v[i]>t[len])
               t[++len]=v[i];
             else{
                int k=binary_seacher(i);
                t[k]=v[i];
            }
        }
        printf("Case %d:\n",++count1);
        if(len==1)printf("My king, at most %d road can be built.\n\n",len);
        else printf("My king, at most %d roads can be built.\n\n",len);
    }
    return 0;
}