PAT Advanced 1067

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

时间限制

100 ms

内存限制

32000 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

关于这道题，首先要注意的是swap函数只能用swap(0,*)，而不是平常我们用的swap(i,j)，也是这个原因，第一次做怎么做都是答案错误。

其次来说一下这道题的思路：

题目暗示的swap次数最少，言外之意就是中间没有过多的过渡交换(指的就是中间某个位置的元素多次为其他位置的元素交换做过渡，

典型的像 汉诺塔问题)。看示例{4, 0, 2, 1, 3}，正常路线就是，4放到a[4]这个位置，就必须把3放到a[3]的位置，就必须把1放到a[1]的位置，

然后逆置过来就是 swap(0,1) -->swap(0,3)-->swap(0,4)，说白了就是一个交换链。可以发现我们访问元素4次(2已经就位)，交换3次。如果

整个链路中没有0怎么办(0已经就位)，我们就需要将0重新调入到链路中来完成交换，这样交换次数应该为n+1次(增加两次0的换入和换出)。

具体代码如下：

#include <stdio.h>
#define MAX 100005
int a[MAX];
int visit[MAX];

int dfs(int x)
{
	int count=0;
	while(!visit[x])
	{
		visit[x]=1;
		count++;
		x=a[x];
	}
	return count;
}

int main()
{
	int n,j;
	scanf("%d",&n);
	for(j=0;j<n;j++)
		scanf("%d",&a[j]);

	int result=0;

	for(j=0;j<n;j++)
	{
		int count=dfs(j);
		if(count !=1 && count !=0)
			result += count+1;
	}

	/* 假设所有的环路中都不含0，这是都是默认的count+1次 */
	/* 在判断一下是否0会出现在某一个环中 */
	if(a[0]!=0)
		result -= 2;

	printf("%d",result);
}