传送门：

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 (≤) 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:

103 5 7 2 6 4 9 0 8 1

Sample Output:

9 题目大意：给定n个数字(1到n)，且每次只能跟0交换，问换成递增的最少步数。 思路： 核心是让每次交换尽量都把0和当前0这个位置的数组下标，这两个数换位置，这样就不浪费这一次交换。 记录下每个元素所在的位置存入数组pos，即pos数组存放的是pos[number]=ard,表示Number这个数字当前在ard这个位置 如果0不在第0个位置，那么每次可以交换0位置和0所在位置在递增之后应该有的元素。 比如说4 0 3 1 2。先把0和pos[0]，即0和1交换，这样1就在它本来应该在的位置。数组变成了4 1 3 0 2，再交换，直到0回到了下标0这个位置。 这样一趟下来保证了每次操作都是有意义的，即每次交换都能把一个元素放回它应该在的位置。 如果这个元素这样交换下来，还没在它应该在的位置，即pos[number]!=number，那就让它去0呆着，下次交换会把它放回应该属于它的位置的。 参考博客： 代码：

#include
     
      using namespace std;int pos[100001]; int main(){    int n;    scanf("%d",&n);    for(int i = 0 ; i < n ; i ++){        int x;        scanf("%d",&x);        pos[x] = i;    }    int cnt = 0;    for(int i = 0; i < n ; i ++){        if(pos[i] != i){            while(pos[0] != 0){                swap(pos[0],pos[pos[0]]);cnt++;            }//如果0不在数组下标为0这个位置，那可以不停的交换0所在位置数组下标 和 0这两个元素。             if(pos[i] != i){                swap(pos[0],pos[i]);                cnt++;            }        }    }    printf("%d\n",cnt);}