从0开始学算法--排序（1.11最小成本排序）

问题：一个升序数组，交换两个数的代价是两个数字之和，求使数组升序的最小代价

解：不难发现要使交换次数最少两两交换后，会形成若干个“环”，那么对于每个环来说，每次都用最小的数字和其他数字交换得到的代价总是最小的。

　　但是这样只是解决了一部分问题还有另外一种情况，那就是可以让环里的最小值和整个数组的最小值先交换，再用最小值交换环内的数字，最后再交换回去。对于每一个环枚举两种情况，选出代价较小的方案即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

const int maxn=1e5+10;
const int vmax=1e5+10;
int n,a[maxn],s;
int b[maxn],t[vmax];
int solve(){
    int ans=0;
    bool vis[maxn];
    for(int i=0;i<n;i++){
        b[i]=a[i];
        vis[i]=false;
    }
    sort(b,b+n);
    for(int i=0;i<n;i++){
        t[b[i]]=i;
    }
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        int cur=i;
        int S=0;
        int m=vmax;
        int an=0;
        while(1){
            vis[cur]=true;
            an++;
            int v=a[cur];
            m=min(m,v);
            S+=v;
            cur=t[v];
            if(vis[cur])break;
        }
        ans+=min(S+(an-2)*m,m+S+(an+1)*s);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    s=vmax;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        s=min(s,a[i]);
    }
    int ans=solve();
    printf("%d\n",ans);
    return 0;
}

从0开始学算法--排序（1.11最小成本排序）

相关推荐