HDU 1070 Milk 完整解析

多品牌牛奶，每品牌給出價格、容量。約束：① 單瓶最多喝 5 天 ② 每天至少 200ml ③ 不足 200ml 棄置。求最便宜品牌，平價選容量最大者。

核心邏輯：計算「每天成本」

有效天數 days = min(volume / 200, 5)（整數除法）。
若 days == 0（容量 < 200），直接捨棄。
單位成本 cost_per_day = price / days。
按 cost_per_day 升序排，相同按 volume 降序。

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

struct Milk {
    string brand;
    double price, volume;
    int days;
    double ratio; // price per day
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector a;
        for (int i = 0; i < N; i++) {
            Milk m; cin >> m.brand >> m.price >> m.volume;
            if (m.volume < 200) continue; // 不足一天量
            m.days = min((int)(m.volume / 200), 5);
            m.ratio = m.price / m.days;
            a.push_back(m);
        }
        
        if (a.empty()) { cout << '\n'; continue; }
        
        sort(a.begin(), a.end(), [](const Milk& x, const Milk& y) {
            if (fabs(x.ratio - y.ratio) > 1e-9) return x.ratio < y.ratio;
            return x.volume > y.volume;
        });
        
        cout << a[0].brand << '\n';
    }
    return 0;
}

關鍵點總結

• 有效天數上限 5：min(vol/200, 5)
• 容量 < 200 直接捨棄：無法滿足一天需求
• 浮點比較：用 fabs 判斷 ratio 相等
• 平價選大容量：次關鍵字 volume 降序
• 多測資：外層 T 循環