CF1685D1 Permutation Weight (Easy Version) 做题记录

给定一个 $1\sim n$ 的排列 $p$。

对于一个 $1\sim n$ 的排列 $q$，定义其权值为：

$|q_1-p_{q_2}|+|q_2-p_{q_3}|+|q_3-p_{q_4}|+\cdots+|q_{n-1}-p_{q_n}|+|q_n-p_{q_1}|$

找出 任意一个 权值最小化的 $1\sim n$ 的排列 $q$。

$2\le n\le 200$。

设 $w_{q_{i\operatorname{mod}n+1}}=q_i$，那么我们要最小化的东西就变成了 $\sum\limits_{i=1}^n|w_i-p_i|$。

一个朴素的想法是让 $w_i=p_i$，但是注意到 $i\to w_i$ 必须要形成一个大环，也就是说 $w$ 导出的置换环只能有一个，所以 $w_i=p_i$ 可能不合法。

那么考虑调整，找到 $w_i$ 和 $w_j$ 在值域上相邻且 $i$ 和 $j$ 来自不同置换环的 $(i,j)$，注意到 $|w_i-w_j|$ 一定是 $1$。这时交换 $w_i$ 和 $w_j$ 就可以以 $2$ 的代价合并两个置换环。这样构造的答案是 $2(c-1)$，其中 $c$ 是 $w$ 的置换环个数。

容易证明这个是下界。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int S=205;

int n,a[S];
int cnt,bel[S];
bool vis[S];
vector<int> vec[S];
pair<int,int> pri[S];
int b[S],nxt[S];

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	for(int i=1;i<=n;i++)
	{
		cnt=0;
		for(int j=1;j<=n;j++) vis[j]=false,vec[j].clear();
		for(int j=1;j<=n;j++)
		{
			if(!vis[j])
			{
				vec[++cnt].push_back(j);
				bel[j]=cnt;
				vis[j]=true;
				j=a[j];
				while(!vis[j])
				{
					vec[cnt].push_back(j);
					bel[j]=cnt;
					vis[j]=true;
					j=a[j];
				}
			}
		}
		for(int j=1;j<=n;j++) pri[j]=make_pair(a[j],j);
		sort(pri+1,pri+n+1);
		for(int j=1;j<=n-1;j++)
		{
			int x=pri[j].second,y=pri[j+1].second;
			if(bel[x]!=bel[y])
			{
				swap(a[x],a[y]);
				swap(b[x],b[y]);
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) nxt[b[i]]=i;
	printf("%d ",1);
	int u=nxt[1];
	while(u!=1)
	{
		printf("%d ",u);
		u=nxt[u];
	}
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}