HDU 5527 Too Rich：貨幣兌換與最優支付策略

題意

有 10 種面額貨幣（1,5,10,20,50,100,200,500,1000,2000），每種給定張數。需支付 X 元，可多付再找零。找零時銀行遵循「優先大面額、張數為偶數」原則（20、500 元特殊）。求最多能使用多少張鈔票完成交易。

解法核心

• 枚舉 20 元和 500 元鈔票的使用張數（0..持有量），這兩種面額在找零規則中有特殊性。
• 對其餘面額：若不限制張數則全用；若受限則用最大偶數張（模擬銀行找零邏輯）。
• 計算總支付額，若 ≥ X，嘗試從大面額向小面額「退回」多付部分，退回時亦遵守偶數張規則。
• 若能精確退回至 X，更新最大張數答案。

代碼框架

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int val[11] = {0,1,5,10,20,50,100,200,500,1000,2000};
int num[11], vis[11], use[11];
int X, ans; long long sum;

int solve() {
    memset(use, 0, sizeof(use));
    if (vis[5] > num[5] || vis[8] > num[8]) return 0; // 20元是第5種，500元第8種
    long long paid = vis[5]*val[5] + vis[8]*val[8];
    int used = vis[5] + vis[8];
    for (int i=1;i<=10;i++) {
        if (vis[i] == -1) { // 不限制
            use[i] = num[i];
            paid += 1LL*use[i]*val[i];
            used += use[i];
        } else { // 限制為偶數張
            use[i] = num[i] - vis[i];
            if (use[i] % 2) use[i]--;
            paid += 1LL*use[i]*val[i];
            used += use[i];
        }
        if (paid >= X) {
            long long change = paid - X;
            for (int j=i;j>=1;j--) {
                long long back = min((long long)use[j], change / val[j]);
                if (vis[j] != -1 && (back % 2)) back--; // 受限面額退回也要偶數
                used -= back;
                change -= back * val[j];
                if (change == 0) { ans = max(ans, used); return 0; }
            }
        }
    }
    return 0;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &X);
        memset(vis, -1, sizeof(vis));
        sum = 0;
        for (int i=1;i<=10;i++) { scanf("%d", &num[i]); sum += 1LL*num[i]*val[i]; }
        if (sum < X) { puts("-1"); continue; }
        ans = -1;
        // 枚舉 20 和 500 的使用量
        for (vis[5]=0; vis[5]<=num[5]; vis[5]++)
            for (vis[8]=0; vis[8]<=num[8]; vis[8]++)
                solve();
        printf("%d\n", ans);
    }
    return 0;
}