Codeforces D. Valera and Swaps（置换群）

题意：

给你一个函数$F(p)$表示把一个排列$p$，变回$1,2,3...n$需要的最小交换次数，然后给你一个长度为n的排列p和一个整数m，让你实现交换最少次数，使得交换后的排列满足$F(x)=m$，如果有多种交换方案，输出字典序最小的

题解：

我们知道把一个排列$p$变为$1,2,3...n$的最小次数=n-环数。
那么现在我们就只需要增加或减少环即可。

我们先跑出一个环数，根据$n$和环数的差值和m比较的结果来决定是加环还是减环。

加环：交换一个环内任意两个点

减环：交换两个不同环内的点

然后暴力枚举交换最小的即可。

AC代码：

#include
using namespace std;
const int MAXN = 3050;
int nxt[MAXN],col[MAXN],tot,n,m;
inline void solve(){tot=0; for(int i=1;i<=n;i++) col[i]=0;for(int i=1;i<=n;i++){if(!col[i]){++tot;for(int j=i;!col[j];j=nxt[j]) col[j]=tot;}}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&nxt[i]);solve();scanf("%d",&m);if(m==n-tot) { puts("0");return 0; }int ans,op=0;if(m>n-tot) ans=m-n+tot,op=1;//环少，应该加环else ans=n-tot-m;printf("%d\n",ans);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!ans) break;if(i!=j && (col[i]!=col[j] ? 1:0)==op){swap(nxt[i],nxt[j]); ans--;printf("%d %d ",i,j);solve();}}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！