浙大城院程序设计竞赛 F【Permutation】
Permutation
https://ac.nowcoder.com/acm/contest/12986/G
题目大意：给出n的俩种排列的数组a和b，对于每一次操作可以选择向前移动一位然后在末尾添加一个任意的数字，或者直接修改一个数字为另外一个数字（包括自己），问最少要几次操作可以使得a变到b
我们知道，每一次移动都可以修改后面的值使得a,b俩个数组对齐，那么只要我a中数字在b中所对应的位置在a之前（或者同一个位置），那么我们可以通过直接往前移动x位使得数字对齐，且在移动的过程中可以直接使末尾的x位直接对齐，那么我们通过贪心策略，就是对于每一个数字，只要b的位置在a之前，那么就记录一下这个数字和a中的位置之差，通过vis数组得到哪一个差值出现的次数最多，那么，那个数字就是我们想要的那个差值
即步数==tmp+n-(vis[tmp]+tmp)==n-vis[tmp]
以下是示意图和代码
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
const int maxn=1e6+5;
int a[maxn],b[maxn],pos[maxn],vis[maxn],ans;
int main()
{
int n=read();
ans=n;
rep(i,1,n) a[i]=read();
rep(i,1,n) b[i]=read(),pos[b[i]]=i;
rep(i,1,n)
{
int tmp=i-pos[a[i]];
if(tmp>=0)
{
vis[tmp]++;
ans=min(n-vis[tmp],ans);
}
}
printf("%d\n",ans);
}
