Cow Sorting

Time Limit: 2000MS Memory Limit: 65536K

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

3
2
3
1

Sample Output

7

Hint

2 3 1 : Initial order.
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).

思路：

一道置换的问题，首先就是交换两个元素，然后不断交换，最后位置就是排序后的位置，首先就是要记录原来未排序的位置，然后进行排序，这样就如a的位置是b的位置而b的位置是a这样就会出现一个循环，然后用这个循环进行判断，首先有两种方法判断：
1.用元素中的最小值，不断进行交换，因为在这个是一个圈！！！所以就将就将最小的提取出来每一个肯定都不在原来的位置，所以每一个都要进行交换，所以要最小的话，就用最小的原来的狡猾比如3 1 2，将1和2交换，2回到了应该的位置，然后1和3交换，那么都回到原来的位置，假如先把1归位的话，无论是2还是3，最后都要互相交换，就变成5+3或者5+4更大。
2.就是和元素中的整个序列中的最小值交换，我就举个例子吧，比如，1 101 102 103 100，1是在原来的位置，但是1比100小太多太多了，先用1置换100，然后用1和其他元素置换肯定比100换其他的小的多。
最后比较这两种那个来的小（ans += min(sum - minn + (len - 1) * minn, sum + minn + (len + 1) * small);）代码中的给我化简了，没有这个容易理解。

#include <iostream>
#include <algorithm>
using namespace std;
struct NODE {
	int id;
	int sum;
	bool friend operator < (NODE a, NODE b) {
		return a.sum < b.sum;
	}
};
NODE node[10010];
bool book[10010] = {false};
int main() {
	int n, small = 0x7fffffff, ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &node[i].sum);
		node[i].id = i;
		small = min(small, node[i].sum);
	}
	sort(node + 1, node + n + 1);
	for (int i = 1; i <= n; i++) {
		if (book[i] == false) {
			int minn = 0x7fffffff, j = i, cnt = 0, sum = 0;
			while (book[j] == false) {
				book[j] = true;
				cnt++;
				minn = min(node[j].sum, minn);
				sum += node[j].sum;
				j = node[j].id;
			}
			ans += sum + min((cnt - 2) * minn, (cnt + 1) * small + minn);
		}
	}
	cout << ans << endl;
	return 0;
}