题目描述

农夫JOHN准备把他的头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要秒来交换脾气值为和的两头牛。
请帮JOHN计算把所有牛排好序的最短时间。

输入描述:

第1行： 一个数，。
第行： 每行一个数，第行是第头牛的脾气值。

输出描述:

第1行： 一个数，把所有牛排好序的最短时间。

示例1

输入
3
2
3
1
输出
7

解答

涉及到群论的相关知识请自行百度，根据群论，置换可以分解为s个不相交循环的乘积，例如初始状态8 4 5 3 2 7，目标状态2 3 4 5 7 8，则可以分解为两个循环的乘积(8 2 7) ( 4 3 5)。对于任意一个循环  ，设它的长度为 ，循环内所有元素的和为， 为使交换的代价尽量小，我们让循环中最小的元素  参与所有的交换，其他元素只各参加一次，总花费为。
例如刚才的栗子(8 2 7)，其中2是其中最小的数。由于2占据了7的位置，所以2和7交换，得到序列8 4 5 3 7 2，这时2占据了8的位置，故2和8交换，得到序列2 4 5 3 7 8。此时循环里的各个数都到达了目标位置，称该循环已完成。
但是上述方法不一定最优，因为我们可以借助循环外的数来辅助交换，先让  和  个数中的最小值  交换，让  进入循环，并和剩下的  个元素各交换一次把它们送入目标位置，最后再让  和 交换并退出循环，此时总花费为，它有可能比第一种方法更优，举个栗子：初始状态1 8 9 7 6，目标为 1 6 7 8 9，它可以分解为(1) (8 6 9 7)，第一个循环只有一个元素，忽略；第二个循环如果按照第一种方法，花费为，而第二种方法花费仅为，第二种方法操作如下：
最优方案
操作数    结果序列        说明
1,6        6,8,9,7,1    全局最小进入循环
1,9        6,8,1,7,9    1占据9的目标位置
1,7        6,8,7,1,9    1占据7的目标位置
1,8        6,1,7,8,9    1占据8的目标位置
1,6       1,6,7,8,9    1退出循环，6重新进入

综合两种方法，总花费为：
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define inf 0x3f3f3f3f
const int N = 1e5 + 7;
typedef long long ll;
int a[N], tmp[N], vis[N], pos[N], mi;
int main()
{
    int n; scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%d",&a[i]), tmp[i] = a[i];
    sort(a + 1, a + 1 + n); mi = a[1];
    for(int i = 1; i <= n; i++)
        pos[a[i]] = i;
    ll sum, ans = 0; int k = 0;
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            int p = i, m = a[i];
            sum = 0, k = 0;
            while(!vis[p])
            {
                vis[p] = 1;
                k++;
                sum += a[p];
                m = min(m, a[p]);
                p = pos[tmp[p]];
            }
            ans += sum + min(m * (k - 2), m + mi * (k + 1));
        }
    }
    cout << ans << endl;
}

来源：sugarbliss