CF1685D1 Permutation Weight (Easy Version) 做题记录

给定一个 1n1\sim n 的排列 pp

对于一个 1n1\sim n 的排列 qq,定义其权值为:

q1pq2+q2pq3+q3pq4++qn1pqn+qnpq1|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}|

找出 任意一个 权值最小化的 1n1\sim n 的排列 qq

2n2002\le n\le 200

wqimodn+1=qiw_{q_{i\operatorname{mod}n+1}}=q_i,那么我们要最小化的东西就变成了 i=1nwipi\sum\limits_{i=1}^n|w_i-p_i|

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

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

容易证明这个是下界。

代码如下:

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