nlogn 最长上升子序列二分优化 部分测试过求助
查看原帖
nlogn 最长上升子序列二分优化 部分测试过求助
190694
木洛楼主2021/3/7 20:26
#include <iostream>
#include <algorithm>
using namespace std;
int n,len,len2;
int a[105],f[105],b[105],c[105];
int bfind(int x)
{
    int L=1,R=len,mid;
    while(L<=R){
        mid=L+(R-L)/2;
        if(b[mid]>=x){
            R=mid-1;
        }else{
            L=mid+1;
        }

    }
    return L;

}

int bfind2(int x)
{
    int L=len2,R=n,mid;
    while(L<=R){
        mid=L+(R-L)/2;
        if(c[mid]>=x){
            R=mid-1;
        }else{
            L=mid+1;
        }

    }
    return R;
}
int main()
{


    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        }
    //正着走一遍
    f[1]=len=1,b[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>b[len]){
            b[++len]=a[i];
        }else if(a[i]==b[len]){}
        else{
        int j=bfind(a[i]);
        b[j]=a[i];
        }

        f[i]=len;
    }
	//反着来一遍
	len2=n,c[n]=a[n];
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<c[len2]){
            c[--len2]=a[i];
        }else if(a[i]==c[len2]){}
        else{
            int j=bfind2(a[i]);
            c[j]=a[i];
        }

        f[i]+=(n-len2);

    }

    cout<<n-*max_element(f+1,f+n+1)+1;


    return 0;
}

如题,该怎么修改,

2021/3/7 20:26
加载中...