排序代价

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 sillysort.in 输出文件 sillysort.out

【问题描述】

有一列数，要对其进行排序(升序)。排序只能通过交换来实现。每次交换，可以选择这列数中的任意两个，交换他们的位置，并且交换的代价为这两个数的和。排序的总代价是排序过程中所有交换代价之和。现要求计算，对于任意给出的一列数，要将其排成升序所需的最小代价。

【输入】

输入包含多组数据。每组数据有两行组成。第一行一个数n，表示这列数共有n个数组成。第二行n个互不相同的整数(都是小于1000的正整数)，表示这列数。输入文件以n＝0结尾。

【输出】

对于每组输入数据，输出组号和排序所需的最小代价。

【样例】

sillysort.in

3

3 2 1

4

8 1 2 4

5

1 8 9 7 6

6

8 4 5 3 2 7

0

sillysort.out

Case 1：4

Case 2：17

Case 3：41

Case 4：34