最小成本排序（ALDS1_6_D:Minimum Cost Sort）

待更新

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn=1e3+5;
const int N=1e4+5;

int n,minn=N,s[maxn],b[maxn],book[maxn],weizhi[N];

int solve()
{
    int ans=0;
    sort(b,b+n);
    for(int i=0;i<n;i++){
        weizhi[b[i]]=i;
    }
    for(int i=0;i<n;i++){
        if(book[i]){
            continue;
        }
        int cnt=0,temp=0,cixiao=N,cur=i;
        while(1){
            book[cur]=1;
            temp+=s[cur];
            cnt++;
            cixiao=min(s[cur],cixiao);
            cur=weizhi[s[cur]];
            if(book[cur]){
                break;
            }
        }
        ans+=min(temp+(cnt-2)*cixiao,temp+cixiao+(cnt+1)*minn);
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
        b[i]=s[i];
        minn=min(s[i],minn);
    }
    int ans=solve();
    cout<<ans<<endl;
    return 0;
}
/*
5
1 5 3 4 2
6
2 1 8 10 7 9
*/