# PAT 解题报告 1067. Sort with Swap(0,*) (25)

### 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.

### 1067. Sort with Swap(0,*)算法分析：

(1) 如果A[0] != 0, 那么A[0]将是需要调整的数字, 从A[0]开始必然可以找到上述例子中的循环, 然后进行调整, 调整以后A[0] = 0

(2) 如果A[0] == 0, 那么从其他非正确位置的数字开始找到的循环一定不包含A[0], 但是因为我们只能使用Swap(0, *) , 所以需要先把A[0] = 0和非正确位置循环中的数交换, 那么交换以后的情况就变成了(1)的情况, 继续模拟.

```#include <cstdio>
#include <vector>
#include <algorithm>

int swapZero(std::vector<int> &nums) {
int cnt = 0;
int tmp1 = 0;
int tmp2 = nums[tmp1];
nums[0] = 0;
while(tmp2 != nums[tmp2]) {
tmp1 = nums[tmp2];
nums[tmp2] = tmp2;
tmp2 = tmp1;
++cnt;
}
return cnt;
}

int gao(std::vector<int> &nums) {
int len = nums.size();
int res = 0;

for(int i = 0; i < len; ++i) {
if(nums[i] != i) {
if(0 != i) {
std::swap(nums[0], nums[i]);
res += 1;
}
res += swapZero(nums);
}
}
return res;
}

int main() {
int n;
std::vector<int>  nums;
scanf("%d", &n);
nums.resize(n);
for(int i = 0; i < n; ++i)
scanf("%d", &nums[i]);
printf("%d\n", gao(nums));
return 0;
}
```

Written on October 13, 2013