链接：https://ac.nowcoder.com/acm/contest/12548/J
来源：牛客网
题目描述
As a master of parallel computing, schwer is recently considering about the method to achieve quick sorting on parallel computers. He needs your help!
Given a permutation (p1,⋯ ,pn)(p1,⋯,pn), you need to sort the permutation with minimum number of rounds. In a single round, one can take many pairs of integers (x1,y1),⋯ ,(xk,yk)(x1,y1),⋯,(xk,yk) as long as the values of x1,y1,⋯ ,xk,ykx1,y1,⋯,xk,yk are pairwise distinct. Then with the help of kk CPUs, for each i∈[1,k]i∈[1,k], the value of pxipxi and pyipyi will be switched immediately. Note that a permutation (p1,⋯ ,pn)(p1,⋯,pn) is sorted if for every integer i∈[1,n]i∈[1,n], pi=ipi=i holds.
Take some examples. Assume that n=4n=4. For p=(1,2,3,4)p=(1,2,3,4), the minimum number of round is 00 as it is already sorted. For p=(4,3,2,1)p=(4,3,2,1), the answer is 11, as you can swap the indices (1,4)(1,4) and (2,3)(2,3) simultaneously.
输入描述:
he first line of input contains a single integer n(1≤n≤105)n(1≤n≤105), indicating the length of the permutation.The second line contains nn integers p1,...,pn(1≤pi≤n)p1,...,pn(1≤pi≤n), the given permutation. It is guaranteed that these integers form a permutation, that is, for every integer i∈[1,n]i∈[1,n] there exists an unique integer j∈[1,n]j∈[1,n] such that pj=ipj=i.
输出描述:
The first line of output should contain a single integer mm, the minimum number of rounds to get the permutation sorted. Then print mm line to show one possible solution.The ii-th of the next mm lines should describe the ii-th round of your solution, beginning with a single integer kk, and followed by 2k2k integers x1,y1;⋯ ;xk,ykx1,y1;⋯;xk,yk. The constraints that 1≤xi,yi≤n1≤xi,yi≤n and the 2k2k integers are pairwise distinct must be held.
示例1
输入
复制
4
1 2 3 4
输出
复制
0
示例2
输入
复制
4
4 3 2 1
输出
复制
1
2 1 4 2 3
这个题和之前蓝桥杯交换瓶子那个题有点像https://www.cnblogs.com/lipoicyclic/p/13959642.html，不过还是看了题解才会的TAT。对于全排列操作使之有序，如果限制交换位置相邻的话方法是逆序对，如果不限制相邻就是找环了。首先易知对于两个点的小环可以第一轮就换过来，这样不会影响后续操作，对于大环比如2 3 4 5 1或者 3 4 1 2，第一轮则要把它拆成多个两个点的小环，然后第二轮换过来。特别注意拆环的时候，如果是偶环直接对称交换，比如3 4 1 2拆完后得到2 1 4 3，如果是奇环也是对称交换，比如2 3 4 5 1得到1 5 4 3 2，这样一定能保证奇数个点归位，剩下的是两个点的小环。
#include <iostream>
#include <vector>
using namespace std;
int n, p[100005], id[100005];
bool vis[100005] = { 0 };
bool ok() {
for(int i = 1; i <= n; i++) {
if(p[i] != i) return false;
}
return true;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> p[i];
id[p[i]] = i;
}
if(ok()) {
cout << 0;
return 0;
}
vector<pair<int, int> > round1;
vector<pair<int, int> > round2;
vector<vector<int> > v;
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
if(p[i] == i) {
vis[i] = 1;
continue;
}
int j = p[i];
if(i == p[j]) {
round1.push_back(make_pair(i, j));
vis[i] = vis[j] = 1;
swap(p[i], p[j]);
id[i] = i, id[j] = j;
} else {
int x = p[i];
vis[i] = 1;
vector<int> tmp;
tmp.push_back(x);
while(x != i) {
vis[x] = 1;
x = p[x];
tmp.push_back(x);
}
v.push_back(tmp);
}
}
if(ok()) {
cout << 1 << endl;
cout << round1.size() << " ";
for(int i = 0; i < round1.size(); i++) {
cout << round1[i].first << ' ' << round1[i].second << ' ';
}
return 0;
}
for(int i = 0; i < v.size(); i++) {//还在round1
//此时奇环处理完后变成偶环了
for(int j = 0; j < v[i].size() / 2; j++) {
round1.push_back(make_pair(id[v[i][j]], id[v[i][v[i].size() - 1 - j]]));
swap(p[id[v[i][j]]], p[id[v[i][v[i].size() - 1 - j]]]);
swap(id[v[i][j]], id[v[i][v[i].size() - 1 - j]]);
}
}
for(int k = 1; k <= n; k++) id[p[k]] = k;
//round2
for(int i = 1; i <= n; i++) {
if(p[i] == i) {
continue;
}
round2.push_back(make_pair(i, p[i]));
swap(p[i], p[p[i]]);
}
cout << 2 << endl;
cout << round1.size() << " ";
for(int i = 0; i < round1.size(); i++) {
cout << round1[i].first << ' ' << round1[i].second << ' ';
}
cout << endl;
cout << round2.size() << " ";
for(int i = 0; i < round2.size(); i++) {
cout << round2[i].first << ' ' << round2[i].second << ' ';
}
return 0;
}