HDU 1009 FatMouse' Trade 題解：貪心算法求最大 JavaBean 收益

題目大意

FatMouse 準備了 M 磅貓糧，要與守衛倉庫的貓咪交易 JavaBean。倉庫有 N 個房間，第 i 個房間有 J[i] 磅 JavaBean，需要 F[i] 磅貓糧。可以按比例交易：支付 F[i]×a% 貓糧可獲得 J[i]×a% JavaBean（a 為實數）。求最大可獲得的 JavaBean 總量，精確到小數點後 3 位。

核心洞察：單價排序

每個房間的「性價比」為 `rate = J[i] / F[i]`（每磅貓糧換得的 JavaBean）。為了最大化總收益，應優先選擇單價最高的房間完全交易，直到貓糧耗盡或房間用完。這是典型的**分數背包問題**，貪心策略最優。

算法步驟

1. 讀入 M, N，若 M=-1 結束。
2. 存儲每個房間的 J, F，計算 rate = (double)J / F。
3. 按 rate 降序排序。
4. 遍歷排序後的房間：
   • 若剩餘貓糧 M >= F[i]，全部交易：`ans += J[i]; M -= F[i];`
   • 否則按比例交易：`ans += J[i] * M / F[i]; break;`
5. 輸出 `ans` 保留 3 位小數。

AC 代碼 (C++)

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

struct Room {
    int j, f;
    bool operator<(const Room& other) const {
        return (double)j / f > (double)other.j / other.f; // 降序
    }
};

int main() {
    int M, N;
    while (scanf("%d %d", &M, &N) == 2 && M != -1) {
        vector<Room> rooms(N);
        for (int i = 0; i < N; ++i) scanf("%d %d", &rooms[i].j, &rooms[i].f);
        sort(rooms.begin(), rooms.end());
        double maxBean = 0.0;
        for (int i = 0; i < N; ++i) {
            if (M >= rooms[i].f) {
                maxBean += rooms[i].j;
                M -= rooms[i].f;
            } else {
                maxBean += (double)rooms[i].j * M / rooms[i].f;
                break;
            }
        }
        printf("%.3f\n", maxBean);
    }
    return 0;
}

關鍵點總結

• **分數背包**特徵：物品可分割，貪心選擇單價最高者優先。
• 排序比較函數使用 `double` 避免整數除法截斷。
• 輸入以 `-1 -1` 結束，需處理多測試用例。
• 輸出格式 `%.3f` 確保 3 位小數精度。

複雜度分析

時間：O(N log N) 主要耗在排序。空間：O(N) 存儲房間信息。N ≤ 1000，極易通過。