M_sea

UVA1016 Silly Sort
UVaLuoguVjudge分析首先整个序列中的数互不相同,于是可以将其看作一个置换。对于这种给置换排序的题,可以...
扫描右侧二维码阅读全文
10
2019/09

UVA1016 Silly Sort

UVa

Luogu

Vjudge

分析

首先整个序列中的数互不相同,于是可以将其看作一个置换。

对于这种给置换排序的题,可以考虑循环分解。

为了方便,下面设循环内所有数的和为 $sum$ ,循环大小为 $len$ ,循环内最小值为 $nmn$ ,整个序列的最小值为 $mn$ 。

对于每个循环,显然可以拿 $nmn$ 和其它数交换,此时代价为 $nmn\times(len-1)+sum-nmn$ 。

然而还有一种情况:把 $nmn$ 和 $mn$ 换一下,再把循环内部排好序,最后再换回来。这样子的代价为 $mn\times len+sum+mn+nmn$ 。

每个循环两种情况取 $\min$ 加起来即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10; //并不知道该开多少 qaq

int n;
int a[N],b[N],S[N],p[N],vis[N];

int main() { int _=0;
    while (n=read()) {
        for (re int i=1;i<=n;++i) S[i]=a[i]=read();
        sort(S+1,S+n+1);
        for (re int i=1;i<=n;++i) b[i]=lower_bound(S+1,S+n+1,a[i])-S;
        for (re int i=1;i<=n;++i) p[b[i]]=i;
        int mn=2e9,ans=0;
        for (re int i=1;i<=n;++i) mn=min(mn,a[i]),vis[i]=0;
        for (re int i=1;i<=n;++i) {
            if (vis[i]) continue;
            int nmn=2e9,sum=0,len=0;
            for (re int j=i;!vis[j];j=p[j])
                ++len,nmn=min(nmn,a[j]),sum+=a[j],vis[j]=1;
            ans+=min(nmn*(len-2)+sum,mn*len+sum+mn+nmn);
        }
        printf("Case %d: %d\n\n",++_,ans);
    }
    return 0;
}
最后修改:2019 年 09 月 10 日 08 : 30 PM

发表评论