CF584E Anton and Ira 做题记录

给定两个排列 sspp,每次可以交换 pp 中的两个数,代价为它们间的距离,问最小代价使 pp 变为 ss。输出方案。

1n20001\le n\le 2000

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

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

考虑如何取到这个下界,不难发现,只要保证 ii 移动的时候只往 posipos_i 的方向移动就行了,也就是 posi<ipos_i<iii 只向左运动,posi>ipos_i>iii 只向右运动,posi=ipos_i=iii 不动就行了。那么考虑按照 posipos_i 从大到小逐个操作,先让 posipos_i 大的归位,那么操作到 ii 的时候若 i=posii\not=pos_iii 一定要向右运动,并且 posipos_i 一定要向左运动;而 posposipos_{pos_i} 要么 i\le i,要么存在 j[posposi,posi]j\in[pos_{pos_i},pos_i] 满足 posj<posposipos_j<pos_{pos_i}。所以设 tmptmp 为当前 ii 运动到的位置,我们总能找到满足 j>tmpj>tmpposj<tmppos_j<tmpjj 来让 tmptmpjj 交换。因为这样做每个 ii 都只会往 posipos_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;
}