[PAT解题报告] Sort with Swap
简单题，对一个0到(n-1)的排列排序，允许的操作是把一个数和0交换。
首先，假设任意两个数可以交换，次数其实就是每个（圈长-1)的总和。
什么叫做圈呢？
就是a应该在b的位置，b应该在c的位置，c应该在d的位置。。。。最后一个数应该在a的位置，这个圈假设包含m个元素，我们交换(m -
1)次，每次可以把一个元素放在正确的位置上，并且最后m个数肯定都在自己的位置了……所以题目等价于找圈。
对于这个题，多了一个条件，我们只能和0交换。
如果我们找到一个圈0，在圈里，我们可以每次用0和某一个交换，同样(m - 1)次之后，所有数在自己的位置。
如果0不在圈里，我们可以现交换一次把0换进来，把x换出去，然后同样(m -
1)次后，所有数到了自己的位置,0到了x应该在的位置，再把0和x交换一次，使得所有数到达正确位置。
所以总结一下：
找圈，如果圈长是m
(1) 0在圈里，需要(m - 1)次
(2) 0不在圈里，需要(m + 1)次
一个圈一个圈的解决即可。
找圈可以用一个mark数组标记经过了哪些元素，然后x =
a[x]走下去，直到走到一个经过的元素（一定是第一个元素），就找到一个圈。
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
bool mark[100005];
int a[100005];
int give(int x) {
int r = 0;
bool have = false;
for (;!mark[x];++r) {
if (x == 0) {
have = true;
}
mark[x] = true;
x = a[x];
}
return have?(r - 1):((r <= 1)?0:(r + 1));
}
int main() {
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%d",a + i);
}
int answer = 0;
for (int i = 0; i < n; ++i) {
answer += give(a[i]);
}
printf("%d\n",answer);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1067
查看17道真题和解析
