1067 Sort with Swap(0, i) （25 分）

1067 Sort with Swap(0, i) （25 分）

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 (≤10^​5​​ ) 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是初次提交的代码，源代码2是参考博客^[1]修改的代码，虽然源代码1有两个测试点运行超时，但是代码思路发现与源代码2的相似，不同之处在于源代码2<font color="hotpink">以空间换时间，在查询中时间复杂度由O(N)降低为O(1),这也是在对空间要求不高时降低时间复杂度的一种方法</font>。

源代码2由原博客修改if为while得，以便于理解。通过分析发现，当序列中存在m个乱序（元素初始位置不在整个序列排好序后它所在的最终位置上），则最少交换次数是大于等于m，换句话说，算法交换次数越接近m，则此算法越有可能是最少次数交换对应的算法。本题采用贪心算法，有效交换次数是乱序元素的个数，无效交换次数是排序过程中带来的额外交换，只有当每次排序力图将访问的元素一次排到它最终的位置上，这样才能保证无效交换次数最少（这是贪心算法的核心）。

对以上分析阐述了源代码2的合理性和正确性，下面对源代码2做一点理解分析。外层for循环保证访问到每个元素，内层while(i!=a[i])保证本次访问操作中a[i]元素交换到它最终的位置上，在本次操作中也有可能会顺带将其他元素也交换到它对应的最终位置。访问操作的代码理解，0作为哨兵，首先将0所占的位置最终应该存的元素换回该位置，(a[0]表示0当前所在的位置)(这个操作即为有效操作)，这样交换完毕后0会回到0对应的最终位置（即0），此时挑选任一个乱序元素暂存0位置，（这个操作即为无效操作）,本算法选择0元素后面第一个乱序元素。

对源代码2原博客代码先抛出小小的疑问（这个疑问属于自己暂时没理解透代码的意图），原博客在第12行使用的是if,不能保证本次访问的元素一定回到最终位置，但是后续在for大循环中不再访问此元素，那后续如何判断它回到最终位置呢？我想可能是在swap的交换中会访问到这个元素，访问到这个元素就有可能把它交换到最终位置，这里描述的可能有点混乱，可能是我没还想明白，先抛出疑问，日后再看，日后看懂了后可能会发出"啊~这没有问题啊~~，自己当时好笨啊，这都没看懂"，但是隐约觉得原博客的代码一次判断而不用多次判断，最终程序运行的时间理论上会小一些。

源代码2

#include <iostream>
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++) {
        while(i != a[i]) {
            while(a[0] != 0) {
                swap(a[0],a[a[0]]);
                cnt++;
            }
            if(i != a[i]) {
                swap(a[0],a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

源代码1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v,ans;
int f(int a) {
    int pos=0;
    while(pos<v.size() &&v[pos]!=a) pos++;
    return pos;
}
void print() {
    for(int i=0; i<v.size(); i++) {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int n;
    cin>>n;
    v.resize(n),ans.resize(n);
    for(int i=0; i<n; i++) {
        cin>>v[i];
        ans[i]=v[i];
    }
    sort(ans.begin(),ans.end());
    int cnt=0;
    while(1) {
        int p0=f(0);
        if(p0==0) {
            int i=0;
            while(i<n&&i==v[i]) i++;
            if(i==n) break;
            swap(v[0],v[i]);
        } else {
            int p=f(p0);
            swap(v[p0],v[p]);
        }
        cnt++;
//      print();
    }
    cout<<cnt;

    return 0;
}

1. https://www.liuchuo.net/archives/2301 ↩