排序代价

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18: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