第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明），签到题J Parallel Sort

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 i\in [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 i\in [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<bits/stdc++.h>
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 <= n; i++){
		cin>>a[i];  p[a[i]] = i;
	}
	
	int cc = 0;
	for(int i = 1; i <= n; i++){
		if(a[i]!=i)cc= max(cc, 1);
		if(a[a[i]]!=i)cc = 2;
	}
	cout<<cc<<"\n";
	
	while(1){
		int ok = 1;
		for(int i = 1; i <= n; i++)
			if(a[i]!=i){ok=0;break;}
		if(ok==1)break;
		
		cnt = 0;
		for(int i = 1; i <= n; i++){
			if(!vis[i] && a[i]!=i){
				if(a[a[i]]==i){
					if(!vis[a[i]]){
						vis[i] = vis[a[i]] = 1;
						swp(i,a[i]);
					}
				}else{
					vis[i] = 1;
					dfs(i);	
				}
			}
		}
		
		cout<<cnt<<" ";
		for(int i = 1; i <= cnt; i++)
			cout<<x[i]<<" "<<y[i]<<" ";
		cout<<"\n";
		for(int i = 1; i <= n; i++)vis[i]=0;
	}
	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/115443376