链接：

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;

}

巴特西

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

链接：

题意：

思路：

代码：

最新文章

热门文章