为什么这么近就重题了。
题意分析
给出 $1\sim n$ 的两个排列 $a,b$，每次可以将 $a$ 末尾的数取出插入到 $a$ 的任意位置，求最少需要多少次能够将 $a$ 转化为 $b$。
我们可以考虑令 $\large map_{b_i}=i$，那么使 $a$ 按照 $\large map_{a_i}$ 有序即可。
那么不妨令 $\large a_i=map_{a_i}$，则求出至少需要几次能够使 $a$ 有序即可。
显然，对于任意长度为 $m$ 的序列 $c$，我们能够通过 $m$ 次操作将 $c$ 排成任意顺序。
那么对于 $a$，至多也只需要 $n$ 次。
又考虑到最开始肯定会有一段有序，不考虑这一段即可。
必然存在一个数 $k$，满足 $a_1<a_2<a_3<\cdots<a_k$，而 $a_k>a_{k+1}$。
那么找到这一个 $k$，答案即 $n-k$。因为 $n-k$ 个元素都需要移动，特别地，$a_k$ 不需要移动，因为可以直接放在 $a_k$ 两侧。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=200000;
int n,a[N+1],b[N+1],map[N+1];
int query(){
int ans=0;
for(int i=1;i<n;i++){
if(a[i]>=a[i+1]){
ans=n-i;
break;
}
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
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);
map[b[i]]=i;
}
for(int i=1;i<=n;i++){
a[i]=map[a[i]];
}printf("%d\n",query());
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
