HDU 5527 Too Rich - 2015 ACM/ICPC 亞洲區長春站題解

題目背景

HDU 5527 "Too Rich" 是 2015 年 ACM/ICPC 亞洲區長春站的一道題目。題目要求在給定硬幣面額與數量的情況下，找出能湊出指定金額的最大硬幣數量。這是一道經典的貪心與特判結合的問題。

題目分析

硬幣面額固定為：1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000（共 10 種）。給定目標金額 x 以及各面額的硬幣數量，需選擇若干硬幣使其總值恰好等於 x，並使使用的硬幣總數最大化。

初看似乎可以直接用貪心：從大面額到小面額盡量多用。但實際上存在反例，特別是 20 和 50 的組合會導致貪心失效。因此需要對 20 和 50 進行特判枚舉。

解題思路

1. 將 20 元（索引 5）和 50 元（索引 8）的使用數量枚舉所有可行組合（vis[5] 和 vis[8]）。
2. 對於其他面額，若未被枚舉（vis[i] == -1），則全部使用；若已枚舉，則使用剩餘數量中最大的偶數（因為兩張同面額可互換不影響總值）。
3. 計算當前總值 tmp 和硬幣數 tmpn。若 tmp >= x，則嘗試從大面額向小面額「退回」多餘金額，退回時同樣注意 20 和 50 的奇偶性限制。
4. 若能精確退回至 x，更新最大硬幣數 ans。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int val[11] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
int x, T, p, num[11], vis[11], use[11];
int ans = -1;
long long sum;

int solve() {
    memset(use, 0, sizeof(use));
    if (vis[5] > num[5] || vis[8] > num[8]) return 0;
    long long tmp = 1LL * vis[5] * val[5] + 1LL * vis[8] * val[8];
    int tmpn = vis[5] + vis[8];
    for (int i = 1; i <= 10; i++) {
        if (vis[i] == -1) {
            tmp += 1LL * num[i] * val[i];
            tmpn += num[i];
            use[i] = num[i];
        } else {
            use[i] = num[i] - vis[i];
            if (use[i] % 2 == 1) use[i]--;
            tmpn += use[i];
            tmp += 1LL * use[i] * val[i];
        }
        if (tmp >= x) {
            long long chao = tmp - x;
            for (int j = i; j >= 1; j--) {
                if (vis[j] == -1) {
                    long long tui = min(1LL * use[j], chao / val[j]);
                    tmpn -= tui;
                    chao -= tui * val[j];
                } else {
                    long long tui = min(1LL * use[j], chao / val[j]);
                    if (tui % 2 == 1) tui--;
                    tmpn -= tui;
                    chao -= tui * val[j];
                }
                if (chao == 0) {
                    ans = max(ans, tmpn);
                    return 0;
                }
            }
            return 0;
        }
    }
    return 0;
}

int main() {
    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) {
            printf("-1\n");
            continue;
        }
        ans = -1;
        for (int i = 0; i <= num[5]; i++) {
            for (int j = 0; j <= num[8]; j++) {
                vis[5] = i;
                vis[8] = j;
                solve();
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

枚舉 20 和 50 的數量最多 100×100 = 10^4 種，每次 solve() 掃描 10 種面額，總複雜度約 O(T * 10^4 * 10)，完全在時間限制內。

總結

本題關鍵在於發現 20 和 50 的特殊性，通過枚舉這兩種面額的使用數量，將問題轉化為其餘面額的貪心處理。代碼實現時需注意長整型防溢出，以及退回邏輯中的奇偶性約束。