@[Star_Sky_](/user/1046223) 你的想法是对的,这个错误跟二分的边界没有什么问题,主要是二分时的逻辑 `dp[mid] >= p2[i]` 出了问题,应改成 `dp[mid] <= p2[i]`,因为 dp 数组是一个单调递增的,你想要找的是 dp 中最后一个小于等于 ai 的元素,用大于等于就显然会有问题。
by liujiaxi123456 @ 2024-09-20 21:54:33
另外,还有一些小细节,具体可见代码,写的时候建议还是把鲁棒性写高一点。
by liujiaxi123456 @ 2024-09-20 21:56:11
Code:
```
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int n, l, r, mid, cnt, ans;
int p1[100005], p2[100005], mp[100005], dp[100005];
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++)scanf("%d", &p1[i]), mp[p1[i]]=i;
for(int i=1; i<=n; i++)scanf("%d", &p2[i]), p2[i]=mp[p2[i]];
// memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for(int i=1; i<=n; i++){
l=0, r=ans, cnt=0;
while(l<=r){
mid=(l+r)/2;
if(dp[mid]<=p2[i]){
cnt=mid;
l=mid+1;
}
else r=mid-1;
}
ans=max(ans,cnt+1);
dp[cnt+1]=p2[i];
}
printf("%d", ans);
return 0;
}
```
by liujiaxi123456 @ 2024-09-20 21:56:26
还有不懂的话可以问我
by liujiaxi123456 @ 2024-09-20 21:56:47
谢谢大佬
by Star_Sky_ @ 2024-09-21 07:35:36