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 我的天远古帖居然还有人,谢谢您我已经解决了