求助,O(nlogn)仍然TLE

P1439 【模板】最长公共子序列

RuntimeErr @ 2020-10-07 08:48:42

请问有什么可以优化的吗

 #include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,a[N],f[N],p[N],len;
int found(int x){
    int l=1,r=len,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(p[f[mid]]>p[x])r=mid;
        else l=mid-1;
    }
    return l;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int k;
    for(int i=1;i<=n;i++){
        scanf("%d",&k);
        p[k]=i;
    }
    for(int i=1;i<=n;i++){
        if(p[a[i]]>p[f[len]]){
            f[++len]=a[i];
        }else {
            f[found(a[i])]=a[i];
        }
    }
    printf("%d",len);
    return 0;
}

by pocafup @ 2020-10-07 08:50:32

显然不是时间复杂度的锅。。。


by yummy @ 2020-10-07 08:52:19

@RuntimeErr 你的found函数,把l=1,r=2,p[f[mid]]>p[x]带进去,发现了什么?


by RuntimeErr @ 2020-10-07 09:00:43

@yummy 哦哦谢谢dalao,才发现%%%%


by asd1926 @ 2021-01-28 03:09:22

@RuntimeErr 你的二分查找那里l = mid + 1


by RuntimeErr @ 2021-01-28 10:51:25

@asd1926 我的天远古帖居然还有人,谢谢您我已经解决了


|