UVA-1016 Silly Sort

　　题目大意：给定一个长度为n的序列，每次操作可以交换任意两个数的位置，代价为两个数的和，求最小代价，将序列排成有序的。

　　首先，显然需要交换的数一定会形成环：

　　那么对于每一个环，我们有两种选择：方案1.自己解决自己；方案2.找人来帮助解决。

　　　　方案1：用环中的最小值去和其他数交换，代价为环中数字总和+环中最小值 *（环中数字个数 - 2）；

　　　　方案2：用整个数列中的最小值去和环中数交换，代价为环中数字总和+环中最小值 +数列最小值（环中数字个数 + 1）。

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include<bits/stdc++.h>

using namespace std;

int n,S,B[1005],P[1005],Fa[1005],Size[1005],Ans;

struct node {int Num,Id;}A[1005];

bool cmp(node x,node y) {return x.Num<y.Num;}

#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)

char buf[65536],*p1,*p2;

inline int read()

{

    char ch;int x(0);

    while((ch=gc)<48);

    do x=x*10+ch-48;while((ch=gc)>=48);

    return x;

}

inline int GetF(int x)

{

    if(x==Fa[x]) return x;

    return Fa[x]=GetF(Fa[x]);

}

int main()

{

    for(register int _=1;;++_)

    {

        n=read(),Ans=0;if(!n) break;

        for(register int i=1;i<=n;++i) B[i]=A[i].Num=read(),A[i].Id=i,Fa[i]=i,Size[i]=1;

        sort(A+1,A+n+1,cmp),S=A[1].Num;

        for(register int i=1,fx,fy;i<=n;++i)

        {

            fx=GetF(i),fy=GetF(A[i].Id),P[A[i].Id]=i;

            if(fx!=fy) Fa[fy]=fx,Size[fx]+=Size[fy];

        }

        for(register int i=1,x,y,fa,ans,Min;i<=n;++i)

        {

            fa=GetF(i);

            if(!Size[fa]) continue;

            ans=0,Min=1005,x=i,y=Size[fa];

            while(Size[fa]) Min=min(Min,B[x]),ans+=B[x],x=P[x],--Size[fa];

            Ans+=min(ans+Min+S*(y+1),ans+Min*(y-2));

        }

        printf("Case %d: %d\n\n",_,Ans);

    }

    return 0;

}

巴特西

UVA-1016 Silly Sort

最新文章

热门文章