解疑
查看原帖
解疑
1138579
Lazy_Durant楼主2024/4/6 18:48

每次二分找第一个比他大的,不应该接着更新len吗?

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,x,a1[N],a2[N],trans[N],b[N],len;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a1[i]);
		trans[a1[i]]=i;
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&x);
		a2[i]=trans[x];
	}
	for(int i=1; i<=n; i++) {
		if(a2[i]>b[len]) {
			b[++len]=a2[i];
			continue;
		}
		int k=lower_bound(b+1,b+len+1,a2[i])-b;
		b[k]=a2[i];
		//len=k;  这一句为什么不要
	}
	printf("%d\n",len);
	return 0;
}
2024/4/6 18:48
加载中...