Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

PAT 1067. Sort with Swap(0,*)

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

解答

#include <cstdio>

int a[100010], n;

int find(int st) //第一个不在正确位置的地方
{
	for (int i = st; i < n; i++)
		if (a[i] != i) return i;
	return -1;
}

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

	int id = 0, cnt = 0, tem;
	while ((id = find(id)) != -1)
	{
		if (a[0] == 0) //0在正确位置上,暂时换走
			a[0] = a[id], a[id] = 0, cnt++;
		while (a[0] != 0) //0不在正确位置上,则与位置0上的数值对应的位置上的数交换
			tem = a[0], a[0] = a[tem], a[tem] = tem, cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论