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

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 (<=10⁵) 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.

10 3 5 7 2 6 4 9 0 8 1Sample Output:
9
索引數(shù)字反向存儲(chǔ)，每次枚舉第一個(gè)位置是否為0，為0在枚舉未歸位后是否有數(shù)字，沒(méi)有則說(shuō)明已排好
#include<cstdio>#include<algorithm>using namespace std;const int maxn = 1e5 + 10;int main(){	int a[maxn];	int n, temp, k = 1, ans = 0;//k保存未歸位數(shù)的最小值  ans保存交換次數(shù) 	scanf("%d", &n);	int count = n - 1;	for(int i = 0; i < n; ++i)	{		scanf("%d", &temp);		a[temp] = i;	} 	while(1)	{		while(a[0] != 0)		{			swap(a[0], a[a[0]]);//交換0與a[0] 			ans++;			count--;		}		while(k < n)		{			if(a[k] != k)			{				swap(a[0], a[k]);//交換0與k的位置				ans++;				break;			}			++k;		}		if(k == n)      //k到達(dá)最后一個(gè)數(shù)的下一位置，說(shuō)明都已歸位 			break;	}	printf("%d/n", ans);	return 0;}/*    //殊途同歸1using namespace std;const int maxn = 1e5 + 10;int a[maxn], ans, n, k;int main(){	ans = 0, k = 1;	int temp;//temp接收索引, k 代表未歸位的最小數(shù) 	scanf("%d", &n);	int count = n - 1;	for(int i = 0; i < n; ++i)	{		scanf("%d", &temp);		a[temp] = i;		if(temp != 0 && temp == i)			count--;	}	while(count > 0)	{		while(a[0] != 0)		{			temp = a[0];			swap(a[0], a[temp]);			ans++; 		}		for(int i = k; i < n; ++i)		{			if(a[i] != i)			{				swap(a[0], a[i]);				k = i;				ans++;				break;			}			if(i == n-1)			{				printf("%d/n", ans);				return 0;			}		}	}	return 0;}*/
/*           //殊途同歸2int main(){	ans = 0, k = 1;// k 代表未歸位的最小數(shù) 	scanf("%d", &n);	int temp, count = n - 1;//temp接收索引	for(int i = 0; i < n; ++i)	{		scanf("%d", &temp);		a[temp] = i;		if(temp != 0 && temp == i)		{			count--;		}	}	while(count > 0)	{		if(a[0] == 0)		{			while(k < n)			{				if(a[k] != k)				{					swap(a[0], a[k]);					ans++;					break;				}				++k;			}		}		while(a[0] != 0)		{			swap(a[0], a[a[0]]);			ans++;			count--;		}	}	printf("%d/n", ans);	return 0;}*/