POJ 3270 Cow Sorting （置换群）

POJ 3270 Cow Sorting （置换群）

Description

Farmer John’s N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique “grumpiness” level in the range 1…100,000. Since grumpy cows are more likely to damage FJ’s milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y.Please help FJ calculate the minimal time required to reorder the cows.

Input

Line 1: A single integer: N. Lines 2..N+1: Each line contains a single integer: line i+1 describes the grumpiness of cow i.

Output

Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input

3231

Sample Output

7

题意

有 n 头牛，每头牛都有一个独一无二的愤怒值，想要把这些牛根据愤怒值的大小进行排序（从小到大），交换任意两头牛位置所花费的时间是他们的愤怒值之和，求最小的交换时间。

思路

假设

初始状态为： 1 3 4 5 2

结束状态为： 1 2 3 4 5

因为有 1−>1 ，所以 (1) 为一个轮换，另外还有 3−>2−>5−>4 ，所以 (3 4 5 2)

对于每一个长度大于 1

首先，对于轮换中的元素，每一个数字都需要至少交换一次才可以到达目标位置，很明显，我们可以用轮换中最小的元素去交换其他元素这样付出的代价才是最小的，此时的代价为 sum−min+(len−1)∗min

其中 sum 为轮换中所有元素之和， min 为轮换中最小元素， len

另外，还有一种情况，假如一个轮换中的最小元素也很大，反复交换所付出的代价也就会变得非常大了，但是我们可以把其他轮换中的元素（这里取全局最小值为最优）拿来与当前轮换的最小值进行交换，然后继续上面的步骤，计算结束后再交换回去，这样做的代价或许会比原来少一点，此时的代价为 sum−min+(len−1)∗ksmin+2∗(min+ksmin)

最终的答案为所有轮换所计算的最小代价之和。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。