题目描述：

给你一个数字序列（每个数字唯一），每次你可以交换任意两个数字，代价为这两个数字的和，问最少用多少代价能把这个序列按升序排列好。

解题报告：

分割线之间的转载于：http://hi.baidu.com/novosbirsk/blog/item/58c5fcfa46911e9159ee90b9.html

---------------------------------------------------------------------------------------------

题目的具体做法是参考刘汝佳的《算法艺术与信息学奥赛》，代码倒是自己实现的。大概思路是：
1.找出初始状态和目标状态。明显，目标状态就是排序后的状态。
2.画出置换群，在里面找循环。例如，数字是8 4 5 3 2 7
明显，目标状态是2 3 4 5 7 8，能写为两个循环：
(8 2 7)(4 3 5)。
3.观察其中一个循环，明显地，要使交换代价最小，应该用循环里面最小的数字2，去与另外的两个数字，7与8交换。这样交换的代价是：
sum - min + (len - 1) * min
化简后为：
sum + (len - 2) * min
其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字。
4.考虑到另外一种情况，我们可以从别的循环里面调一个数字，进入这个循环之中，使交换代价更小。例如初始状态：
1 8 9 7 6
可分解为两个循环：
(1)(8 6 9 7)，明显，第二个循环为(8 6 9 7)，最小的数字为6。我们可以抽调整个数列最小的数字1进入这个循环。使第二个循环变为：(8 1 9 7)。让这个1完成任务后，再和6交换，让6重新回到循环之后。这样做的代价明显是：
sum + min + (len + 1) * smallest
其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字，smallest是整个数列最小的数字。
5.因此，对一个循环的排序，其代价是sum - min + (len - 1) * min和sum + min + (len + 1) * smallest之中小的那个数字。

-------------------------------------转载完毕-----------------------------------------------

循环的部分可以用一个数组来实现，z[value]表示value这个数字应该在的位置。

然后循环value = x[z[value]]，直到value变回初始值，就得到一个循环。（x是原始的数组序列)

代码入下：

#include<iostream>
#include<algorithm>
using namespace std;
#define size 10000
int n, x[size], y[size], z[100001], vst[size], ans;
int main()
{
    scanf("%d", &n);
    memset(vst, 0, sizeof(int) * n), ans = 0;
    for(int i = 0; i < n; i++)
        scanf("%d", &x[i]), y[i] = x[i];
    sort(y, y + n);
    for(int i = 0; i < n; i++) z[y[i]] = i;
    for(int i = 0; i < n; i++)
    {
        if (!vst[i])
        {
            int ssum = 0, tar = x[i], id = i, len = 0, mmin = 100001;
            while(true)
            {
                ssum += tar, vst[id] = 1;
                if (tar < mmin) mmin = tar;
                id = z[tar];tar = x[z[tar]];len++;
                if (tar == x[i]) break;
            }
            int ans1 = ssum - mmin + (len - 1) * mmin;
            int ans2 = ssum + mmin + (len + 1) * y[0];
            ans += (ans1 > ans2 ? ans2 : ans1);
        }
    }
    printf("%d\n", ans);
    return 0;
}