高等排序——最小成本排序

Minimum Cost Sort

题意：

有重量为 $w_{i} (i=0,1,...,n-1)$ 的n个货物排成一列。现要用机械臂将这些货物排序。机械臂每次操作可以提起货物i和货物j并交换二者位置，同时产生 $w_{i} +w_{j}$ 的成本。机械臂的次数没有限制。请求出将给定货物列按重量升序排列时所需总成本的最小值。

输入：

第一行输入整数n。第二行输入n个整数 $w_{i} (i=0,1,...,n-1)$ 空格隔开。

输出：

在第一行内输出最小值

条件： $1\leq n\leq 1000$ ， $0\leq w_{i} \leq 10^4$ ， $w_{i}$ 的值不重复。

题解：

我们以W={4,3,2,7,1,6,5}为例分析。画一张图，标出移动位置如下：

最小成本排序(例1)

图中我们会发现，出现了几个闭合的圆。分别是

4->7->5->1->4,

3->2->3,

6->6

对每个圆所需最小成本分析：

长度为1的圆，即没有要移动的，成本为0。

长度为2的圆，只需一次交换即可让元素抵达最终位置，所以两个元素的成本和就是成本。

然而长度大于等于3的圆。例如在处理4->7->5->1->4时，则需要使用1来移动其他所有元素才能保证成本最小。

计算最小成本

也就是说，这种情况下的最优方法，是通过圆中最小的值来移动其他元素。

不妨设圆中的元素为 $w_{i}$ ,园内元素数为n，那么此时成本为 $\sum w_{i}+[(n-1)-1]*min(w_{i})=\sum w_{i}+(n-2)*min(w_{i})$

这个方法虽然可以求最小成本，但还存在反例。圈内的各元素值相对较大，如何处理?

图中有圈圈1->2->1的成本为3,8->10->9->7->8的成本为51，但是我们先交换1和7将8->10->9->7->8改为8->10->9->1->8,这部分的成本就成了28+2=30.。然后再加上2次1和7的交换和圆1->2->1的3，总成本为49。

也就是说，有时候也要从圈外借取元素来移动，能让成本降低。

设圈外元素为x。借元素增加的成本为 $2*(min(w_{i})+x)$ ，节约的成本为 $(n-1)*(min(w_{i})-x)$ .。

此时的总成本为

$\sum w_{i}+(n-2)*min(w_{i})+2*(min(w_{i})+x)-(n-1)*(min(w_{i})-x)$

$=\sum w_{i}+min(w_{i})+(n+1)*x$

代码部分：

一些需要的数组、常数定义

找圈圈

主函数