给定两个排列 和 ,每次可以交换 中的两个数,代价为它们间的距离,问最小代价使 变为 。输出方案。
。
遇到这种题一定要考虑答案下界和怎么取到。
首先设 即 要去的位置,那么由于 应该在 而不是 ,并且一次交换最多可以让两个数字归位,所以答案下界为 。
考虑如何取到这个下界,不难发现,只要保证 移动的时候只往 的方向移动就行了,也就是 的 只向左运动, 的 只向右运动, 的 不动就行了。那么考虑按照 从大到小逐个操作,先让 大的归位,那么操作到 的时候若 则 一定要向右运动,并且 一定要向左运动;而 要么 ,要么存在 满足 。所以设 为当前 运动到的位置,我们总能找到满足 且 的 来让 和 交换。因为这样做每个 都只会往 移动,所以答案取到了下界。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
const int S=2005;
struct node
{
int x,y;
}res[S*S];
int n,a[S],b[S];
int pos[S],p[S],id[S];
int tot;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) pos[b[i]]=i;
int ans=0;
for(int i=1;i<=n;i++) ans+=abs((p[i]=pos[a[i]])-i);
for(int i=1;i<=n;i++) id[p[i]]=i;
for(int i=n;i>=1;i--)
{
int pp=id[i];
for(int j=pp+1;j<=i;j++)
{
if(p[j]<=pp)
{
res[++tot]=(node){pp,j};
swap(p[pp],p[j]);
swap(id[p[pp]],id[p[j]]);
pp=j;
}
}
}
printf("%d\n",ans/2);
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
{
printf("%d %d\n",res[i].x,res[i].y);
}
return 0;
}