ACM 發工資問題：貪心算法求最少張數，遞歸與迭代實現

題目：給定金額（正整數），用 100、50、10、5、2、1 元面額找零，求最少張數。經典貪心問題，因面額系統為 canonical coin system，貪心策略（優先用大面額）保證最優解。

遞歸實現（教學用，注意棧溢出風險）

int countNotes(int amount) {
    if (amount == 0) return 0;
    if (amount >= 100) return amount/100 + countNotes(amount%100);
    if (amount >= 50)  return amount/50  + countNotes(amount%50);
    if (amount >= 10)  return amount/10  + countNotes(amount%10);
    if (amount >= 5)   return amount/5   + countNotes(amount%5);
    if (amount >= 2)   return amount/2   + countNotes(amount%2);
    return amount; // 剩餘 1 元
}

迭代實現（工程推薦，O(1) 空間）

int countNotes(int amount) {
    int[] denom = {100, 50, 10, 5, 2, 1};
    int count = 0;
    for (int d : denom) {
        count += amount / d;
        amount %= d;
    }
    return count;
}

完整 ACM 輸入輸出處理

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n && n != 0) { // 讀取測試用例數，0 結束
        int total = 0;
        for (int i = 0; i < n; i++) {
            int salary; cin >> salary;
            total += countNotes(salary);
        }
        cout << total << endl; // 每組輸出一行總張數
    }
    return 0;
}

原題輸入輸出示例

Input:
3
1 2 3
0

Output:
4
// 解析：1=1張, 2=1張, 3=2張(2+1)，共 4 張

常見錯誤避坑

• 遞歸版用 static int sum 導致多測試用例累加不歸零，應用返回值累加。
• 輸入讀取邏輯錯誤：int a[m]; for(i) cin>>a[m] 下標越界，應為 a[i]。
• 面額順序必須從大到小，否則貪心失效。

理解貪心證明與邊界條件，此類找零問題即可秒殺。