牛客假日团队赛2 H.奶牛排序

淡淡的烟草味﹌ 2021-12-24 05:13 195阅读 0赞

# 链接： #

[https://ac.nowcoder.com/acm/contest/924/H][https_ac.nowcoder.com_acm_contest_924_H]

# 题意： #

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

# 思路： #

离散化，置换群。  
考虑位置移动会形成一个有向环，将这个环中最小的值挨个与每个值交替，这个环就变成我们需要的顺序了。  
也可以将环中的最小值与环外的最小值交换，用环外的最小值代替交换，每个环选择代价最小的交换方式即可。

# 代码： #

#include <bits/stdc++.h>
    
    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;
    }

转载于:https://www.cnblogs.com/YDDDD/p/11037637.html

[https_ac.nowcoder.com_acm_contest_924_H]: https://ac.nowcoder.com/acm/contest/924/H