记录编号	136832	评测结果	A
题目名称	排序代价	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-11-03 19:26:36	内存使用	0.31 MiB

#include<cstdio>
#include<cstring>
#include<utility>
#include<algorithm>
using namespace std;
pair<int, int> b[1005];
int a[1005], l[1005], s[1005], m[1005], tot, gm;
bool v[1005];
int main(){
	freopen("sillysort.in", "r", stdin);
	freopen("sillysort.out", "w", stdout);
	int n, i, j, t1, t2, ans, test(0);
	while (scanf("%d", &n), n){
		++test;
		tot = 0; gm = 0x3f3f3f3f; ans = 0;
		memset(v, 0, n);
		for (i = 0; i < n; ++i) scanf("%d", &a[i]), b[i] = make_pair(a[i], i);
		sort(b, b + n);
		for (i = 0; i < n; ++i) if (!v[i]){
			s[tot] = m[tot] = a[i]; l[tot] = 1; v[i] = true;
			for (j = b[i].second; !v[j]; j = b[j].second){
				s[tot] += a[j]; ++l[tot]; v[j] = true;
				if (m[tot] > a[j]) m[tot] = a[j];
			}
			if (gm > m[tot]) gm = m[tot];
			++tot;
		}
		for (i = 0; i < tot; ++i){
			t1 = (l[i] - 2) * m[i]; t2 = (l[i] + 1) * gm + m[i];
			ans += t1 < t2? t1 + s[i]: t2 + s[i];
		}
		printf("Case %d: %d\n", test, ans);
	}
	return 0;
}