链接：

题意：

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

请帮JOHN计算把所有牛排好序的最短时间。

思路：

离散化，置换群。

考虑位置移动会形成一个有向环，将这个环中最小的值挨个与每个值交替，这个环就变成我们需要的顺序了。

也可以将环中的最小值与环外的最小值交换，用环外的最小值代替交换，每个环选择代价最小的交换方式即可。

代码：

#include 
    
     using namespace std;typedef long long LL;const int MAXN = 3e5 + 10;const int MOD = 1e9 + 7;struct Node{    int v;    int pos;    bool operator < (const Node& that) const    {        return this->v < that.v;    }}node[MAXN];int n, m, k, t;int Pt[MAXN], Po[MAXN];int A[MAXN], C[MAXN];int Vis[MAXN];int main(){//    freopen("test.in", "r", stdin);    cin >> n;    int mmin = 5e5+10;    for (int i = 1;i <= n;i++)    {        cin >> node[i].v;        node[i].pos = i;        A[i] = node[i].v;        mmin = min(mmin, A[i]);    }    sort(node+1, node+1+n);    int cnt = 1;    C[node[1].pos] = cnt;    for (int i = 2;i <= n;i++)    {        if (node[i].v == node[i-1].v)            C[node[i].pos] = cnt;        else            C[node[i].pos] = ++cnt;    }    LL res = 0;    for (int i = 1;i <= n;i++)    {        if (Vis[i])            continue;        Vis[i] = 1;        if (C[i] == i)            continue;        LL sum = 0;        sum += A[i];        int pos = C[i], tmpmin = A[i];        int num = 1;        while (pos != i)        {            Vis[pos] = 1;            sum += A[pos];            num++;            tmpmin = min(A[pos], tmpmin);            pos = C[pos];        }        LL v1 = 1LL*tmpmin*(num-1)+sum-tmpmin;        LL v2 = 1LL*mmin*(num-1)+sum-tmpmin+2LL*(tmpmin+mmin);        res += min(v1, v2);    }    cout << res << endl;    return 0;}