给定一个 的排列 。
对于一个 的排列 ,定义其权值为:
找出 任意一个 权值最小化的 的排列 。
。
设 ,那么我们要最小化的东西就变成了 。
一个朴素的想法是让 ,但是注意到 必须要形成一个大环,也就是说 导出的置换环只能有一个,所以 可能不合法。
那么考虑调整,找到 和 在值域上相邻且 和 来自不同置换环的 ,注意到 一定是 。这时交换 和 就可以以 的代价合并两个置换环。这样构造的答案是 ,其中 是 的置换环个数。
容易证明这个是下界。
代码如下:
#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;
}