51 nod 1574 排列转换

对于每一个点，如果他的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();
}