题意简述：
给定一个$1$到$n(n<=2000)$的初始排列以及最终排列 我们每次可以选取位置为$i$和$j$的
并交换它们的位置 花费为$ |i-j| $ 求从初始状态变换到末状态所需最小花费
-----------------------------------------------------------------------------------------------------------
比赛时这题留了$40min$ 然而自己贪心策略还是有漏洞
结束后看了首页的官方题解 感觉思路非常值得借鉴
首先 我们把末状态变为到$1～n $初状态也与之相对应地改变 (设为$a[i]$)
比如样例可以变为
$3 2 4 1$
$1 2 3 4$
我们假设每次交换花费为$ 2|i-j| $那么从初始状态到末状态最优的情况下花费即为
$\sum_{i}^{n}|a[i]-i|$
-----------------------------------------------------------------------------------------------------------
已经知道问题的下界了 我们再来考虑是否对于任意情况 总存在一种达到下界花费的方案
我们每次考虑当前状态中值最小且不在对应位置的数 然后找它左边第一个比它位置大的数
然后进行交换 直到它换到自己的目标位置
我们会发现 按照这样的换法 所有数都一直在向着目标位置移动 没有往返过
所以花费就是最小的 即 $\sum_{i}^{n}|a[i]-i|$
另外由于交换次数给的范围比较大 $(n^{2}/2)$ 刚好是比极限情况（$n$到$1$排列）稍大
于是这题做到这里就可以解决了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int a[N],pos[N];
int ans1[N*N>>],ans2[N*N>>];
int n,k,ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d",&a[i]);
int x;
for(int i=;i<=n;++i)
{
scanf("%d",&x);
pos[x]=i;
}
for(int i=;i<=n;++i)
a[i]=pos[a[i]];
for(int i=;i<=n;++i)
{
int j=i;
while(a[j]!=i)
++j;
while(j!=i)
{
int l=j-;
while(a[l]<j)
--l;
ans+=j-l;
++k;
ans1[k]=l;
ans2[k]=j;
swap(a[l],a[j]);
j=l;
}
}
printf("%d\n%d\n",ans,k);
for(int i=;i<=k;++i)
printf("%d %d\n",ans1[i],ans2[i]);
return ;
}