奶牛排队

  最近在想学学算法啥的,就在学校图书馆借了一本《趣题学算法》,草草看一看感觉蛮不错的,书上用的是伪代码,所以并没有实现具体的代码,但是重要的是思考的方法。不多说,直接上一波原题:

  Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help FJ calculate the minimal time required to reorder the cows.

Input:
Line 1: A single integer: N.
Lines 2.. N+1: Each line contains a single integer: line i+1 describes the grumpiness of cow i.

Output:
Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input:

3
2 3 1
6
4 3 1 5 2 6

Sample Output:

7
18

Hint:
2 3 1 : Initial order.
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).

没用的介绍

  本体题意要求我们将奶牛根据他们的暴脾气指数(索引)从小到大排序,并且要求交换的代价最少。(代价=交换的一对奶牛暴脾气指数的和)。这涉及到置换问题,所以需要一点置换群的小知识。

  关于置换群:置换群是由置换组成的群。即n元集合Ω到它自身的一个一一映射,称为Ω上的一个n元置换或n阶置换。Ω上的置换可表示为:
σ = \left( \begin{array}{ccc} α_k \\ α_{i_k} \\ \end{array} \right)
  差不多就这样吧,有点深奥,我讲不清楚emmmmm,具体就自己去学吧。

假装题解

  我们把一个数列转换为多个置换环(即,目标顺序与当前顺序之间元素交换的小集合)。然后记录每个环中的极小值、环的长度 以及环的所有元素,那么我们就有了俩中情况:

  • 一种是(8 2 7)(4 3 5),这里面包含俩环。这种环所需要的 代价 = sum + (len - 2) * min(sum为这个环所有数字的和,len为长度,min为这个环里面最小的数字)
  • 还有一种是(1)(8 6 9 7)。这种环我们需要特殊处理,即把1和另一个环的极小值交换,然后计算代价,之后再换回来。则代价 = sum + min + (len + 1) * smallest (sum为这个环所有数字的和,len为长度,min为这个环里面最小的数字,smallest是整个数列最小的数字)

  所以我们就可以得出俩中情况中的最优解,即哪一种代价小就是答案。最后我们需要一个hash哈希结构来保存元素位置的对应关系。方便我们反向查找。

假代码

//
// Created by CongTsang on 2018/6/10.
//

#include <iostream>
#include <algorithm>
using namespace std;

const int NMAX = 10010;
int cow[NMAX];
int scow[NMAX];
int Hash[100010];
bool vis[NMAX];

int main() {
    int N;
    int MIN = 0xfffffff;
    cin>>N;
    memset(vis, false, sizeof(vis));

    for (int i = 0; i < N; ++i) {// init
        cin>>cow[i];
        scow[i] = cow[i];
        if (MIN > cow[i]) MIN = cow[i];
        Hash[cow[i]] = i;
    }

    sort(scow, scow+N); // target
    int len, minimum, i;
    int length=N;
    int ans=0;

    while (length) {
        i=len=0;
        int sum=0;
        minimum = 0xfffffff;
        while (vis[i]) i++; // find the start point
        int begin = i;

        while (true) { // Replacement ring, split group
            len++;
            vis[i] = true;
            if (minimum > cow[i]) minimum = cow[i];
            sum += cow[i];

            i = Hash[scow[i]];
            if (i == begin) break;
        }

        length -= len;
        if (len == 1) continue; // just one element
        int v1 = (len - 2) * minimum;
        int v2 = minimum + (len + 1) * MIN;
        ans += (v1 < v2) ? v1 : v2; // choose the min
        ans += sum;
    }
    cout<<ans<<endl;
    return 0;
}

  POJ,这是代码提交器,注意不要复制粘贴就是干,请尊重自己。


爱狂笑的孩子运气不会差