您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 3262 Protecting the Flowers：貪心排序優化總損失

編輯：C++ 入門

題目大意

N 朵花，每朵有枯萎速度 Dᵢ 和保護時間 Tᵢ。每次只能保護一朵花，保護時其他花持續枯萎。求保護順序使總損失最小。

數學建模

若順序為 π，總損失 = 2 × Σ(D_{πᵢ} × Σ_{j

相鄰交換法：比較 i、j 相鄰時的順序影響

i 在 j 前：貢獻 = 2 × (Dᵢ × Tⱼ + ...)
j 在 i 前：貢獻 = 2 × (Dⱼ × Tᵢ + ...)

i 應在 j 前 ⇔ Dᵢ/Tᵢ > Dⱼ/Tⱼ

完整代碼

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

struct Flower { long long d, t; } a[100010];

bool cmp(const Flower& x, const Flower& y) {
    return x.d * y.t > y.d * x.t;  // 避免浮點，交叉相乘比較
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%lld%lld", &a[i].d, &a[i].t);
        
        sort(a, a + n, cmp);
        
        long long ans = 0, time_sum = 0;
        for (int i = 0; i < n; i++) {
            ans += 2 * time_sum * a[i].d;
            time_sum += a[i].t;
        }
        printf("%lld\n", ans);
    }
    return 0;
}