对于每一个点,如果他的p[i]=s[i],则不需要移动,如果在p序列中的位置在s序列中的左边,则p需要移动,在移动的过程中对于每一个需要向右移动的就都可以替换。同理向左的时候也是如此
4 4 2 1 3 3 2 4 1
p4在s4的左边,p2不需要移动,p1在s1的左边,p3在s3的右边,最优情况是每次都不进行重复的
1<->3交换 4<->3其实我们把路径画出来就可以找到规律。
#include<bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; typedef double dl; const int N = 2e5+7; const int M = 1e9+7; const int INF = 0x7fffffff; int n,m; int p[N],s[N]; int st[N]; map <int,int> mp1; map <int,int> mp2; void solve() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]),mp1[p[i]]=i; for(int i=1;i<=n;i++) scanf("%d",&s[i]),mp2[s[i]]=i; ll sum=0; for(int i=1;i<=n;i++) { sum+=abs(mp1[i]-mp2[i]); } printf("%lld",sum/2); } int main() { solve(); }