PAT Sort with Swap(0, i)

1067 Sort with Swap(0, i)

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

总结：自己是真滴蠢，怎么就是想不到怎么做呢？？？

自己代码：

 题目中所给的例子是可以顺利执行的，但是 遇到 1 0 3 5 7 2 4 9 8这样顺序的，就出错了，早早的就结束了排序

#include 
using namespace std;
 
const int N=100010;
int a[N],b[N];//a用来存储题目给出的数据的顺序，b存储a[i]在a数组中的位置
int n;
 
int main(){
    int cot=0;
    scanf("%d",&n);
    
    for(int i=0;i
        scanf("%d",&a[i]);
        b[a[i]]=i;
    }
    
    if(b[0]!=1){//如果0所在的位置不是1的话，需要把0交换到位置1
        int temp=a[1];
        swap(a[1],a[b[0]]);
        swap(b[0],b[temp]);
        cot++;
    }
    
    while(a[0]!=0){
        swap(a[b[b[0]]],a[b[0]]);
        b[0]=b[b[0]];
        cot++;
    }
    
    for(int i=0;iprintf("%d ",a[i]);
    puts("");
    printf("%d\n",cot);
    
    return 0;
}

还是多学习学习大佬的代码！ 

#include 
using namespace std;
int main() {
    int n, t, cnt = 0, a[100010];
    cin >> n;
    for(int i = 0; i < n; i++){
    	cin >> t;
    	a[t] = i;
    }
    for(int i = 1; i < n; i++) {
        //这样的结构还可以顺便检验序列是否是递增
        if(i != a[i]) {
            while(a[0] != 0) {
                swap(a[0],a[a[0]]);
                cnt++;
            }
            if(i != a[i]) {//反例：3 0 2 1 4  //第一次循环后，a[0]==0 a[1]==1
                //需要继续往下循环，看看下面的数字是否是按序排列的
                swap(a[0],a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

好好学习，天天向上！

我要考研！