Codeforces 題目：獎品兌換模擬（需 64 位整數）

問題背景

題目要求模擬獎品兌換過程。輸入 n（≤ 50）個積分值，每個積分值 ≤ 10^9。有 5 種獎品，價格分別為 cost[0..4]。每獲得一個積分值，累加到總積分 sum 中；當 sum 足夠兌換最便宜獎品時，優先兌換價格最高的可負擔獎品（從 cost[4] 遞減到 cost[0]），兌換盡可能多的該獎品，扣除積分，繼續嘗試兌換，直到 sum < cost[0]。最後輸出 5 種獎品的兌換數量及剩餘積分。

關鍵細節：數據範圍與類型選擇

• n ≤ 50，單次積分 ≤ 10^9，總積分 sum 最大約 5×10^10，需 64 位整數（long long 或 unsigned long long）。
• 獎品數量 cnt[i] 同理可能超過 32 位有符號整數範圍（2^31-1 ≈ 2.1×10^9），必須用 64 位無符號或有符號長整型。
• 輸出格式要求 %llu（無符號長長整數）或 %lld（有符號）。

算法流程

1. 讀入 n，若 EOF 結束。
2. 讀入 n 個積分值到數組 points。
3. 讀入 5 個獎品價格 cost[0..4]。
4. 初始化 sum = 0，cnt[5] = {0}。
5. 遍歷每個積分值 p：
   • sum += p；
   • 當 sum >= cost[0] 時，從 j = 4 遞減到 0：
   • 若 sum >= cost[j]，計算 num = sum / cost[j]；
   • cnt[j] += num; sum -= num * cost[j]; break;（跳出內層循環，重新從最高價獎品嘗試）。
6. 輸出 cnt[0]..cnt[4] 及 sum。

代碼實現（C）

#include <stdio.h>
#include <string.h>

typedef unsigned long long LL;

int n;
int points[60];
int cost[5];
LL cnt[5];
LL sum;

int main() {
    // freopen("input.txt", "r", stdin);  // 本地測試用
    while (scanf("%d", &n) != EOF) {
        memset(points, 0, sizeof(points));
        memset(cost, 0, sizeof(cost));
        memset(cnt, 0, sizeof(cnt));
        sum = 0;
        for (int i = 0; i < n; ++i) scanf("%d", &points[i]);
        for (int i = 0; i < 5; ++i) scanf("%d", &cost[i]);
        for (int i = 0; i < n; ++i) {
            sum += points[i];
            while (sum >= cost[0]) {
                for (int j = 4; j >= 0; --j) {
                    LL num = sum / cost[j];
                    if (num >= 1) {
                        cnt[j] += num;
                        sum -= cost[j] * num;
                        break;
                    }
                }
            }
        }
        printf("%llu %llu %llu %llu %llu\n", cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]);
        printf("%llu\n", sum);
    }
    return 0;
}

複雜度分析

時間 O(n × 5) = O(n)，空間 O(1)。極其輕量。

易錯點總結

1. 整型溢出：務必用 64 位類型存儲 sum 和 cnt。
2. 兌換優先級：必須從最高價獎品向最低價嘗試，且每次兌換後重新從最高價開始（break 只跳出 for j 循環，while 會繼續）。
3. 輸入結束條件：while (scanf("%d", &n) != EOF) 處理多組測試數據。