2845 排序的代价

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+10;
int n,cnt,ans,cas;
int r[N],a[N],b[N],c[N],s1;
int p[N][N],s[N],h[N];
bool vis[N];
int main(){
    while(scanf("%d",&n)==1){
        cnt=ans=0;
        memset(vis,0,sizeof vis);
        memset(p,0,sizeof p);
        memset(h,0,sizeof h);
        for(int i=1;i<=n;i++) scanf("%d",r+i);
        for(int i=1;i<=n;i++) a[i]=r[i];
        sort(a+1,a+n+1);s1=a[1];
        for(int i=1;i<=n;i++) b[a[i]]=i;
        for(int i=1;i<=n;i++) c[i]=b[r[i]];
        for(int i=1,t;i<=n;i++) if(!vis[i]){
            s[++cnt]=r[t=i];
            while(!vis[t]) vis[t]=1,p[cnt][++p[cnt][0]]=r[t],s[cnt]=min(s[cnt],r[t]),h[cnt]+=r[t],t=c[t];
        }
        for(int i=1;i<=cnt;i++){
            ans+=min(s[i]*(p[i][0]-1)+h[i]-s[i],s[i]*2+s1*2+s1*(p[i][0]-1)+h[i]-s[i]);
        }
        if(!ans) break;
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}