HDU 2187 悼念 512：分數背包貪心購買大米

題目背景與模型

地震災區急需糧食，給定經費 n 和 m 種大米，每種有單價 p 和總重量 h。大米可任意分割購買（分數背包），目標：在經費內買到最大總重量。

貪心策略

單價低的大米性價比最高。將所有大米按單價 p 升序排序，依次購買：若經費 ≥ 該米總價 (p×h)，全買；否則用剩餘經費買盡可能多的重量 (n/p)，結束。

代碼實現要點

struct Rice { int p, w; } r[1010];
bool cmp(Rice a, Rice b) { return a.p < b.p; } // 單價升序

sort(r, r+m, cmp);
double ans = 0;
for (int i = 0; i < m && n > 0; ++i) {
    if (1.0 * r[i].p * r[i].w <= n) {
        n -= r[i].p * r[i].w;
        ans += r[i].w;
    } else {
        ans += 1.0 * n / r[i].p;
        break;
    }
}
printf("%.2lf\n", ans);

易錯點提醒

• 排序方向：單價從小到大（便宜優先）。
• 經費、價格、重量均為整數，計算時轉 double 避免整除截斷。
• 循環變量 i 必須在每輪結束時 ++，否則死循環（原博主曾因漏寫 i++ WA 一上午）。
• 輸出保留兩位小數。