1067. Sort with Swap(0,*) (25)

​ 时间限制

​ 150 ms

​ 内存限制

​ 65536 kB

​ 代码长度限制

​ 16000 B

​ 判题程序

​ Standard

​ 作者

​ CHEN, Yue

Given any permutation of the numbers {0, 1, 2,…, N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3} Swap(0, 3) => {4, 1, 2, 3, 0} Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (<=105) followed by a permutation sequence of {0, 1, …, N-1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10 3 5 7 2 6 4 9 0 8 1

Sample Output:

9

题意：只用0交换，看换了多少次

解决方案，画环，含0的环s个，不含0的环k个，最终就为n-s+k-2

或者相加含0的每一个环的个数-1加上不含0的每个环的个数+1就为结果

代码如下：

代码还可改编为寻找含0环交换，不含0环不交换后的顺序

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	vector<int> a(n),t(n);
	int value;
	for(int i=0;i<n;++i){
		scanf("%d",&value);
		a[i]=value;t[a[i]]=i;
	}
	int cnt=0;
	for(int i=0;i<n;++i){
		if(t[i]!=i){
			int flag=0;  //判断是否为含环
			int index=i;
			int temp_index=a[i];
			int cnt_index=0;
			while(t[index]!=index){
				++cnt_index;
				if(a[index]==0) flag=1;
				int temp=t[index];
				if(t[temp]==temp){
					a[index]=temp_index;
				}else{
					a[index]=a[t[index]];		
				}			
				t[index]=index;
				index=temp;	
			}
			
			if(flag==1){
				cnt+=cnt_index-1;
			}else{
				cnt+=cnt_index+1;
			}
		}
	}
	/*
	for(int i=0;i<n;++i){
		printf("%d ",a[i]);
	}*/
	printf("%d",cnt);
	return 0;
}