Poj 3262: Protecting the Flowers

poj3262.md

Poj 3262: Protecting the Flowers

題目

分析

Greedy 策略：d/t 大的先做，也就是 t/d 小的先做。 證明可參 這裡。

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

typedef long long ll;

struct Cow {
    ll t;
    ll d;

    bool operator < (const Cow& c) const {
        // t/d < c.t/c.d
        return t * c.d < d * c.t;
    }
};

int N;
Cow cows[100000];

ll solve() {
    ll d_total = 0;
    for (int i = 0; i < N; i++)
        d_total += cows[i].d;

    sort(cows, cows + N);

    ll cnt = 0;
    for (int i = 0; i < N; i++) {
        d_total -= cows[i].d;
        cnt += 2 * cows[i].t * d_total;
    }

    return cnt;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%lld %lld", &cows[i].t, &cows[i].d);

    printf("%lld\n", solve());

    return 0;
}