CF584E Anton and Ira 做题记录

给定两个排列 $s$ 和 $p$，每次可以交换 $p$ 中的两个数，代价为它们间的距离，问最小代价使 $p$ 变为 $s$。输出方案。

$1\le n\le 2000$。

遇到这种题一定要考虑答案下界和怎么取到。

首先设 $pos_i=j|s_j=p_i$ 即 $p_i$ 要去的位置，那么由于 $p_i$ 应该在 $pos_i$ 而不是 $i$，并且一次交换最多可以让两个数字归位，所以答案下界为 $\frac{\sum\limits_{i=1}^n|i-pos_i|}{2}$。

考虑如何取到这个下界，不难发现，只要保证 $i$ 移动的时候只往 $pos_i$ 的方向移动就行了，也就是 $pos_i<i$ 的 $i$ 只向左运动，$pos_i>i$ 的 $i$ 只向右运动，$pos_i=i$ 的 $i$ 不动就行了。那么考虑按照 $pos_i$ 从大到小逐个操作，先让 $pos_i$ 大的归位，那么操作到 $i$ 的时候若 $i\not=pos_i$ 则 $i$ 一定要向右运动，并且 $pos_i$ 一定要向左运动；而 $pos_{pos_i}$ 要么 $\le i$，要么存在 $j\in[pos_{pos_i},pos_i]$ 满足 $pos_j<pos_{pos_i}$。所以设 $tmp$ 为当前 $i$ 运动到的位置，我们总能找到满足 $j>tmp$ 且 $pos_j<tmp$ 的 $j$ 来让 $tmp$ 和 $j$ 交换。因为这样做每个 $i$ 都只会往 $pos_i$ 移动，所以答案取到了下界。

代码如下：

#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;
}