POJ 3085 Quick Change：貪心找零最少硬幣數

POJ 3085 Quick Change：貪心找零

給定 1~500 美分的找零金額，用 25、10、5、1 美分硬幣找零，要求硬幣總數最少。多測試用例，輸出各面額硬幣數量。

解題思路

美國硬幣系統為 canonical，貪心策略（優先使用大面額）保證最優。依次用 25、10、5、1 除取商作為該面額數量，餘數繼續處理下一面額。

代碼實現

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n, m, i;
    int f[4] = {25, 10, 5, 1};
    while (scanf("%d", &n) != EOF && n) {
        for (i = 1; i <= n; i++) {
            int k[4] = {0};
            scanf("%d", &m);
            while (m >= f[0]) { m -= f[0]; k[0]++; }
            while (m >= f[1]) { m -= f[1]; k[1]++; }
            while (m >= f[2]) { m -= f[2]; k[2]++; }
            while (m >= f[3]) { m -= f[3]; k[3]++; }
            printf("%d %d QUARTER(S), %d DIME(S), %d NICKEL(S), %d PENNY(S)\n", i, k[0], k[1], k[2], k[3]);
        }
    }
    return 0;
}

極簡模板題，注意輸出格式完全匹配。