*A1067 Sort with Swap(0, i)

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805403651522560
贪心算法的题大多都是要有一个最佳策略的，这就导致不知道策略的人很难写出正确答案，这道题一定要注意一下，虽然代码不长。

策略

最核心的一步是用0所在的pos[i] 与i交换

代码

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    int N, left = 0;
    int ans = 0;
    scanf("%d",&N);
    vector<int> a(N), pos(N);//
    for(int i = 0; i < N; i++){
        scanf("%d",&a[i]);
        pos[a[i]] = i;
        if(a[i]!=i&&a[i]!=0)left++;
    }
    int k = 1;
    while(left>0){
        if(pos[0] == 0){
            while(k < N){
                if(pos[k]!=k){
                    swap(pos[0],pos[k]);
                    ans++;
                    break;
                }
                k++;
            }
        }
        while(pos[0]!=0){
            swap(pos[0],pos[pos[0]]);//将0和pos[0]交换
            ans++;
            left--;
        }
    }
    printf("%d",ans);
    return 0;
}

柳的代码：https://www.liuchuo.net/archives/2301
不使用left记录，使代码更简洁，当哨兵回到自己位置的时候，交换一次

#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++) {
        if(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;
}