HDU 4952 Poor Mitsui：貪心相鄰交換法證明最優處理順序

問題描述

有 n 項任務，每項有 a_i (處理時間) 和 b_i (懲罰係數)。初始容量 V。處理任務 i 時，若當前容量 v ≤ a_i 則失敗。否則容量變為 v - a_i，總懲罰增加 b_i / (v - a_i)。求任務順序使總懲罰最小。n ≤ 40。

貪心策略：相鄰交換法證明

考慮相鄰任務 i, j。設處理 i 前容量為 v。
順序 i→j 懲罰：b_i/(v-a_i) + b_j/(v-a_i-a_j)
順序 j→i 懲罰：b_j/(v-a_j) + b_i/(v-a_j-a_i)
比較兩者，經代數變形得：
i→j 優於 j→i ⇔ b_i/a_i < b_j/a_j ⇔ b_i·a_j < b_j·a_i

故按 b/a 升序排序（即 b_i·a_j < b_j·a_i）即為最優序。這是經典的「相鄰交換法」證明貪心最優性。

特殊情況處理

• b_i = 0：懲罰為 0，放在最前（不影響後續容量）
• 若存在 a_i ≥ V：無論順序如何，處理該任務時容量必 ≤ a_i，無解 → 輸出 -1

C++ 實現

#include 
#include 
using namespace std;
struct Task { int a, b; } t[45];

bool cmp(Task x, Task y) {
    return 1LL * x.b * y.a < 1LL * y.b * x.a; // b/a 升序
}

double solve(Task t[], int n, int V) {
    for (int i=0; i= V) return -1; // 必須 b>0 才構成威脅
    double ans = 0, v = V;
    for (int i=0; i