problem
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 (p_1,cdots,p_n)(p
1
,⋯,p
n
), you need to sort the permutation with minimum number of rounds. In a single round, one can take many pairs of integers (x_1,y_1),cdots,(x_k,y_k)(x
1
,y
1
),⋯,(x
k
,y
k
) as long as the values of x_1,y_1,cdots,x_k,y_kx
1
,y
1
,⋯,x
k
,y
k
are pairwise distinct. Then with the help of kk CPUs, for each iin [1,k]i∈[1,k], the value of p_{x_i}p
x
i
and p_{y_i}p
y
i
will be switched immediately. Note that a permutation (p_1,cdots,p_n)(p
1
,⋯,p
n
) is sorted if for every integer iin [1,n]i∈[1,n], p_i=ip
i
=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.
solution
//题意：给出一个排列，每次可以交换任意对数(a[i],a[j])，求最小交换次数让其变成升序，并输出每次交换的数对
//思路：对于每个环:如果环中只有两个数,那么一次交换即可.如果环中超过两个数,那么两次交换即可比如(2,3,,,n,1),只需要两步(1,n,n-1,,,,2),(1,2,3,,,n)就可以有序，如4567123,3217654,1234567。因为无序序列是由若干个独立环交换后形成的，所以答案最多两次交换，构造环的时候每次去查找即可。
#include
using namespace std;
const int maxn = 1e5+10;
int a[maxn], p[maxn], vis[maxn];
int x[maxn], y[maxn], cnt;
void swp(int i, int j){
x[++cnt] = i; y[cnt] = j;
swap(a[i],a[j]);
p[a[i]] = i; p[a[j]] = j;
}
void dfs(int i){
if(a[a[i]]!=i){
int j = a[i], k = p[i];
swp(j,k);
vis[j] = vis[k] = 1;
dfs(k);
}
}
int main(){
int n; cin>>n;
for(int i = 1; i >a[i]; p[a[i]] = i;
}
int cc = 0;
for(int i = 1; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
