HDU 2021 發工資找零：貪心算法求最少鈔票數

題目大意

給定 n 個工資額，面額 {100, 50, 10, 5, 2, 1}，每人用最少張數找零，求總張數。多測試用例，n=0 結束。

貪心策略證明

面額系統為規范貨幣系統：每個面額都是較小面額的整數倍（或組合），貪心策略（優先用大面額）保證最優解。

代碼實現

#include <iostream>
using namespace std;

int main()
{
    int n, i, num[100], sum, j;
    int mon[6] = {100, 50, 10, 5, 2, 1};
    while (cin >> n && n != 0) {
        for (i = 0; i < n; i++) cin >> num[i];
        sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < 6; j++) {
                while (num[i] >= mon[j]) {
                    num[i] -= mon[j];
                    sum++;
                }
            }
        }
        cout << sum << endl;
    }
    return 0;
}

優化：除法替代循環

for (j = 0; j < 6; j++) {
    sum += num[i] / mon[j];
    num[i] %= mon[j];
}

• 時間復雜度從 O(金額/最小面額) 降為 O(面額種類數)。
• 邏輯更清晰，無副作用修改原數組（可用臨時變量）。

擴展思考

• 若面額系統非規范（如 {100, 50, 30, 1}），貪心失效，需動態規劃（完全背包）求最優解。
• 輸出每種面額張數：增加計數數組 cnt[6] 記錄。