O(nlogn)怎么T了？？dalao求助！

Dark_Van @ 2019-02-01 21:07:11

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100010;

int n,a[MAXN],b[MAXN];
int c[MAXN];
int stack[MAXN];
int ans=1;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;i<=n;j++)
            if(b[j]==a[i]){
                c[j]=i;
                break;
            }
    stack[1]=c[1];
    for(int i=2;i<=n;i++){
        if(stack[ans]<c[i]){
            stack[++ans]=c[i];
        }else{
            stack[lower_bound(stack+1,stack+ans+1,c[i])-stack]=c[i];
        }
    }
    printf("%d",ans);
    return 0;
}

by xiaolou @ 2019-02-01 21:09:16

@Dark_Van

    for(int i=1;i<=n;i++)
        for(int j=1;i<=n;j++)

这是O（nlogn）？！。。。（笑哭）

by Dark_Van @ 2019-02-01 21:10:14

@xiaolou 但是求LIS的部分是nlogn啊

by Dark_Van @ 2019-02-01 21:10:30

怎么优化啊...Orz

by xiaolou @ 2019-02-01 21:12:00

@Dark_Van 整段代码的时间复杂度取决于其中时间复杂度最高的一段代码

by Dark_Van @ 2019-02-01 21:12:56

@xiaolou 怎么优化啊，，， 请dalao指教！

by xiaolou @ 2019-02-01 21:13:34

我的做法是把b数组映射到a数组，这样最长公共子序列就变成了一个最长上升子序列，然后O（nlogn）求，亲测O（n^2）会T

by xiaolou @ 2019-02-01 21:14:33

还用了一个二分。。。

by xiaolou @ 2019-02-01 21:15:06

大概这个样：

    for(int i=1;i<=n;i++)
    {
        cin >> b[i];
        dp[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++)
    {
        if(m[b[i]]>dp[ans])
        {
            ans++;
            dp[ans]=m[b[i]];
        }
        else
        {   
            int l=0,r=ans;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(dp[mid]>m[b[i]])
                    r=mid;
                else
                    l=mid+1;
            }
            dp[l]=min(m[b[i]],dp[l]);
        }
    }

by Dark_Van @ 2019-02-01 21:22:40

A了，蟹蟹dalao

优化了一下映射方法

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100010;

int n,a[MAXN],b[MAXN];
int c[MAXN];
int stack[MAXN];
int ans=1;
int qwq[MAXN];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        qwq[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        c[i]=qwq[b[i]];
    }
    stack[1]=c[1];
    for(int i=2;i<=n;i++){
        if(stack[ans]<c[i]){
            stack[++ans]=c[i];
        }else{
            stack[lower_bound(stack+1,stack+ans+1,c[i])-stack]=c[i];
        }
    }
    printf("%d",ans);
    return 0;
}

by 什么叫中二呀 @ 2019-02-11 22:24:04

LCS真的能转LIS吗?

Hank:

5
5 1 3 2 4
1 5 2 4 3