# PAT-A 真题 – 1067 Sort with Swap(0, i)

Given any permutation of the numbers {0, 1, 2,..., }, 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  nonnegative integers.

### Input Specification:

Each input file contains one test case, which gives a positive  () followed by a permutation sequence of {0, 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 <bits/stdc++.h>
using namespace std;
vector<int> arr, pos(100010);
int swap_cnt = 0;
void _swap(int &a, int &b){
swap_cnt++;
swap(a, b);
}

bool Judge(){
for(static int i = 0; i < arr.size(); i++){
if(arr[i] != i){
swap(pos[arr[0]], pos[arr[i]]);
_swap(arr[0], arr[i]);
return true;
}
}
return false;
}

int main(){
int cnt;
scanf("%d", &cnt);
arr.resize(cnt);
for(int i = 0; i < cnt; i++){
scanf("%d", &arr[i]);
pos[arr[i]] = i;
}
while(arr[0] || Judge()){
_swap(arr[pos[0]], arr[pos[pos[0]]]);
swap(pos[0], pos[pos[0]]);
}
printf("%d\n", swap_cnt);
return 0;
}