LA 6530 Football 詳解

題目：給定 n 場比賽結果（主隊進球 x，客隊進球 y），初始積分：勝 3 分、平 1 分、負 0 分。擁有 m 個「購買進球」機會，每花 1 單位可將任意一場比賽的主隊進球 +1。求最大化總積分。n≤100, m≤100。

貪心策略：按「邊際收益」排序

1. 已獲勝場次：無需投入，直接 +3 分。
2. 其餘場次：計算「使獲勝/平局所需進球數」：
   - 當前 x ≤ y。
   - 獲勝需 need_win = y - x + 1。
   - 平局需 need_draw = y - x（若 x==y 則 0）。
3. 排序規則：按 need_win 升序（同值 need_draw 升序）。直觀上：成本最低的優先買獲勝，因為勝 3 分 > 平 1 分，單位成本收益最高。
4. 分配過程：遍歷排序後的場次：
   - 若 m ≥ need_win：買獲勝，m -= need_win，積分 +3。
   - 否若 m ≥ need_draw：買平局，m -= need_draw，積分 +1。
   - 否則停止。
5. 剩餘場次：若仍有 m>0 但無法買勝/平，檢查是否有 need_draw==0（原本平局）的場次，每場 +1 分（但這在排序中已處理）。

正確性論證

將每場比賽視為「項目」，投入資源換取收益（3/1/0）。獲勝的邊際收益為 3 分，成本 c_w；平局收益 1 分，成本 c_d（c_d = c_w - 1）。
單位成本收益：獲勝 3/c_w，平局 1/c_d。證明可知 3/c_w ≥ 1/c_d 恒成立（因 c_w = c_d+1，3/(c_d+1) ≥ 1/c_d ⇔ 3c_d ≥ c_d+1 ⇔ 2c_d ≥ 1，對 c_d≥1 成立；c_d=0 時平局免費優先）。
因此優先投資獲勝，且成本越低越優先，即按 need_win 升序貪心選擇，得到全局最優。

參考代碼 (C++)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        int ans = 0;
        vector need_win;
        for (int i = 0; i < n; ++i) {
            int x, y; cin >> x >> y;
            if (x > y) ans += 3;
            else need_win.push_back(y - x + 1); // 獲勝所需進球
        }
        sort(need_win.begin(), need_win.end());
        for (int w : need_win) {
            int d = w - 1; // 平局所需
            if (m >= w) { m -= w; ans += 3; }
            else if (m >= d) { m -= d; ans += 1; }
            else break;
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵測試用例

複雜度分析

總結

LA 6530 是「資源分配最大化收益」的貪心經典模型。關鍵在於證明單位成本收益遞減，從而確立「按獲勝成本升序優先買勝」的最優策略。此類「購買進球/投票/廣告投放」問題，核心皆為計算邊際收益率並排序貪心。