sillysort.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream.h>
#include <iostream.h>
#include <string.h>
#include <stdlib.h>

ifstream fin("sillysort.in");
ofstream fout("sillysort.out");
#define cout fout

const int MAX = 1000+5;

int n, a[MAX], b[MAX], used[MAX];

int cmp(const void* e1, const void* e2) {
	return *((const int*)e1) - *((const int*)e2);
}

main() {
	int icase = 0;
	for (; fin >> n;) {
		if (n == 0) break;
		int i, j;
		for (i = 1; i <= n; i++)
			fin >> a[i];

		memcpy(b, a, sizeof(a));
		qsort(&b[1], n, sizeof(int), cmp);
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++)
				if (a[j] == b[i])
					break;
			a[j] = -i;
		}
		for (i = 1; i <= n; i++)
			a[i] = -a[i];

		int tot = 0;
		memset(used, 0, sizeof(used));
		for (i = 1; i <= n; i++) if (!used[i]) {
			int sum = b[i], min = b[i], count = 1;
			used[i] = 1;
			for (j = a[i]; j != i; j = a[j]) {
				if (b[j] < min) min = b[j];
				sum += b[j];
				used[j] = 1;
				count++;
			}
			if (sum + min * (count - 2) < sum + min + b[1] * (count + 1))
				tot += sum + min * (count - 2);
			else
				tot += sum + min + b[1] * (count + 1);
		}

		cout << "Case " << ++icase << ": " << tot << endl << endl;
	}

 	return 0;
}