Codeforces 264A Caisa and Sugar 詳細題解

Codeforces 264A Caisa and Sugar 題目分析與解法

題目背景： Caisa 想買糖果，商店有 n 種糖，第 i 種售價 a 元 b 分。Caisa 有 s 元錢，只能買一種。商店找零規則：不足 1 元的部分以糖果代替（最多 99 顆），且優先找整元。求最多能獲得多少顆糖果，若無法購買輸出 -1。

核心觀察

• 若單價 a > s，直接無法購買。
• 若 a == s 且 b == 0，剛好付清，找零 0 顆糖果（但可作為可行解）。
• 若 a < s 或 a == s 且 b > 0，找零的分數部分為 (100 - b) % 100 顆糖果。

算法流程

1. 讀入 n, s。
2. 初始化 ans = 0，標記 flag = true 表示是否存在可行購買。
3. 遍歷 n 種糖果：讀取 a, b。若 a > s 跳過；若 a == s && b == 0 則 flag = false；否則計算 candies = (100 - b) % 100，更新 ans = max(ans, candies) 並設 flag = false。
4. 若 flag 仍為真，輸出 -1；否則輸出 ans。

參考代碼

#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int n, s;
    while (~scanf("%d%d", &n, &s)) {
        s *= 100; // 轉為分
        int flag = 0, a, b, ans = 0;
        while (n--) {
            scanf("%d%d", &a, &b);
            int cost = a * 100 + b;
            // 只買一種，故 j=1 即可
            if (cost <= s) {
                flag = 1;
                ans = max(ans, (s - cost) % 100);
            }
        }
        printf("%d\n", flag ? ans : -1);
    }
    return 0;
}

複雜度分析

時間複雜度 O(n)，空間複雜度 O(1)。n ≤ 100，極輕鬆通過。

常見錯誤提醒

• 忘記處理 a == s 且 b == 0 的情況（雖然糖果數為 0，但屬於可行解）。
• 將錢轉為分時未乘 100，導致比較錯誤。
• 找零糖果計算公式錯誤，應為 (100 - b) % 100 而非 100 - b（當 b=0 時應為 0）。