华中农业大学第六届程序设计大赛网络同步赛 J.幻化(思维)

晚上chipizz同学突然问我这道题,然后我口胡了一下先把a数组的i位变成i然后再把b改成对应映射再求逆序数
然而第一个样例就不对・(PД`q。)・゜・

emmm,事实上是自己思路有问题,i,j位置的数字交换不等效与一位一位swap过去.

对于i,j两个位置的数字交换后,单个数而言的最小cost如下所示

\[
\color{black}{cost=\frac{|i-j|}{2}}
\]

这一点很容易想到,但事实上大部分数不是一步到位的,这里我们假设di是ai到di的距离,我们设

\[
\color{black}{ans=\sum_{i=1}^nd_i}
\]


实际上,每一次i到ai中必定存在一个posx<=i,我们每次交换ai和posx的数字x,然后再从pos=x的位置交换到a_i位置便可得到最优解,
实际上也不用考虑这么麻烦,我们可以想象一下每一次交换之后ans都在减小,说明每一次交换并不会增加我们要的cost.
结合之前的部分正确想法,我们可以得到

\[
\color{black}{conv_{a_i}=i}
\]

那么实际上

\[
\color{black}{cost=\frac{1}{2}\sum_{i=1}^n|i-conv_{b_i}|}
\]

代码就很简单啦

#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<limits.h>
#include<string.h>
#include<map>
#include<list>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define inf int(0x3f3f3f3f)
#define mod int(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1

int a[200005];
int b[200005];

int conv[200005];

int n;

int main()
{
    int zu;
    scanf("%d",&zu);
    while(zu--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),conv[a[i]]=i;
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans+=abs(i-conv[b[i]]);
        printf("%lld\n",ans/2);
    }
}