Codeforces 387B George and Round：貪心策略最小化新增題目

問題描述

George需準備一場至少n道題的比賽，要求包含複雜度恰好為a₁

貪心策略

核心思想：盡可能用現有題目滿足要求，從簡單到困難匹配。

算法步驟

1. 兩個數組均已排序（題目給定）
2. 雙指針遍歷：i遍歷要求a，j遍歷現有題b
3. 若b[j] ≥ a[i]，說明第j道題可簡化為第i個要求，匹配成功，i++，j++
4. 若b[j] < a[i]，第j道題太簡單無法滿足當前要求，j++
5. 最終未匹配的要求數量即為答案

代碼實現

int i = 0, j = 0;
while(i < n && j < m) {
    if(b[j] >= a[i]) { // 可滿足要求
        i++; j++;
    } else {
        j++; // 現有題太簡單，跳過
    }
}
cout << n - i << endl; // 未滿足的要求數

樣例驗證

樣例1：a=[1,2,3], b=[1,2,2,3,3]
匹配：1←1, 2←2, 3←3 → 全滿足，答案0

樣例2：a=[1,2,3], b=[1,1,1,1,1]
匹配：1←1, 2無法匹配(剩餘全1), 3無法匹配 → 答案2

樣例3：a=[2,3,4], b=[1]
1無法滿足2 → 答案3

正確性證明

• 貪心選擇性質：對於最小的未滿足要求a[i]，用最小的可用題目b[j]（b[j]≥a[i]）匹配是最優的。若用更大的題目，會浪費資源導致後續更難滿足。
• 最優子結構：匹配後剩餘子問題結構相同。

複雜度

時間O(n+m)，空間O(1)。n,m≤3000，極高效。