护花 (flower. cpp/c/pas)

题目描述

约翰留下他的 \(N (N \leq 100000)\) 只奶牛上山采木．他离开的时候, 她们像往常一样悠 闲地在草场里吃草．可是, 当他回来的时候, 他看到了一幕惨剧: 牛们正躲在他的花园里, 啃食着他心爱的美丽花朵! 为了使接下来花朵的损失最小, 约翰赶紧采取行动, 把牛们送回牛棚. 牛们从 1 到 N 编号. 第 i 只牛所在的位置距离牛棚 \(T_i (1 \leq T_i \leq 2000000)\) 分钟的路程, 而在约翰开始送她回牛棚之前, 她每分钟会啃食 \(D_i (1 \leq Di \leq 100)\) 朵鲜花．无论多么努力, 约翰一次只能送一只牛回棚．而运送第第 \(i\) 只牛事实上需要\(2 T_i\) 分钟, 因为来回都需要时间. 写一个程序来决定约翰运送奶牛的顺序, 使最终被吞食的花朵数量最小.

输入格式

第 \(1\) 行输入 \(N\), 之后 \(N\) 行每行输入两个整数 \(T_i\) 和 \(D_i\)

输出格式

一个整数, 表示最小数量的花朵被吞食

样例输入

6
3 1
2 5
2 3
3 2
4 1
1 6

样例输出

86

样例解释

约翰用 6, 2, 3, 4, 1, 5 的顺序来运送他的奶牛

Explanation

这其实是有一个贪心策略的:

两个奶牛, 如果两个交换, 是不会影响别的奶牛吃花的.

所以只需要比较任意两个奶牛之间吃花的速度就可以了.

然后直接 \(O(n log(n))\) 排序走一遍 (并不能基数排序).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;

class Cow
{
public:
    int id;
    lli time, speed;
} cows[maxn];
bool operator < (Cow a, Cow b) {
    // Two cows won't affect other cows if their sequence changes, adjacently.
    return a.time * b.speed < b.time * a.speed;
}

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        cows[i].id = i;
        scanf("%lld", &cows[i].time);
        scanf("%lld", &cows[i].speed);
    }
    sort(cows + 1, cows + 1 + n);
    // Output results
    lli res = 0, nibble_speed = 0;
    for (int i = n; i >= 1; i--) {
        res += cows[i].time * nibble_speed;
        nibble_speed += cows[i].speed;
    }
    printf("%lld\n", res * 2);
    return 0;
}