Codeforces 557A Ilya and Diplomas：三級獎狀最優分配貪心解

Codeforces 557A 經典貪心問題：n 位參賽者需分配一、二、三等獎狀，每等級有最小/最大數量限制，優先最大化一等獎數量，其次二等、三等。

問題建模

• 總人數：n (3 ≤ n ≤ 3×10⁶)
• 第 i 等獎限制：min[i] ≤ count[i] ≤ max[i]
• 保證可行：Σmin[i] ≤ n ≤ Σmax[i]
• 優先序：最大化 count[1] → count[2] → count[3]

貪心策略

1. 先給每等級分配最小值：ans[i] = min[i]
2. 剩餘名額：rem = n - Σmin[i]
3. 按優先序 (1→2→3) 分配剩餘名額：

for (int i = 1; i <= 3; ++i) {
    int can_add = min(rem, max[i] - min[i]);
    ans[i] += can_add;
    rem -= can_add;
}

C++ 參考實作

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    int mn[4], mx[4], ans[4];
    for (int i = 1; i <= 3; ++i) {
        cin >> mn[i] >> mx[i];
    }
    
    for (int i = 1; i <= 3; ++i) {
        ans[i] = mn[i];
        n -= mn[i];
    }
    
    for (int i = 1; i <= 3; ++i) {
        int add = min(n, mx[i] - mn[i]);
        ans[i] += add;
        n -= add;
    }
    
    cout << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';
    return 0;
}

範例驗證

正確性證明

由於優先序固定且約束為區間，貪心策略在每一步都做出局部最優選擇：優先將剩餘資源分配給最高優先級且未達上限的等級。此問題具有「貪心選擇性質」與「最優子結構」，貪心解即全域最優解。

複雜度分析

• 時間：O(1) — 固定 3 個等級，常數時間
• 空間：O(1) — 固定大小陣列