1833. Maximum Ice Cream Bars

題目 / Problem

中文：炎熱的夏天，一個男孩想買冰淇淋。商店裡有 n 支冰淇淋，給你一個長度為 n 的陣列 costs，其中 costs[i] 是第 i 支冰淇淋的價格（單位是「硬幣」）。男孩一開始有 coins 個硬幣，他想買盡可能多的冰淇淋。男孩可以用任意順序購買。請回傳他最多能買幾支冰淇淋。題目要求你用計數排序（counting sort）來解。

English: On a hot summer day, a boy wants to buy ice cream bars. There are n bars; costs[i] is the price of the i-th bar in coins. The boy starts with coins coins and wants to buy as many bars as possible, in any order he likes. Return the maximum number of bars he can buy. The problem asks you to solve it with counting sort.

Constraints / 限制 - costs.length == n - 1 <= n <= 10^5 - 1 <= costs[i] <= 10^5 ← 價格上限很小，是用計數排序的關鍵 / small price ceiling — the key to counting sort - 1 <= coins <= 10^8 ← 注意：總和可能超過 int 範圍 / note: a running sum can overflow a 32-bit int

Worked example / 範例

costs = [1,3,2,4,1], coins = 7  →  output = 4

買價格為 1、1、2、3 的四支，總花費 1+1+2+3 = 7，剛好用完，買到 4 支。 Buy the bars priced 1, 1, 2, 3 for a total of 7 — exactly all the coins, giving 4 bars.

名詞解釋 / Glossary

貪心 / Greedy：每一步都做「當下看起來最好」的選擇，並且這個局部最優能導出全域最優。這裡：總是先買最便宜的，能讓買到的數量最多。 / At each step take the choice that looks best right now, when that local optimum yields the global optimum. Here: always buy the cheapest available bar to maximize the count.
排序 / Sorting：把元素按大小重新排列。我們需要價格由小到大，才能優先買便宜的。 / Rearranging elements by value. We want prices ascending so we can buy the cheapest first.
計數排序 / Counting Sort：一種不靠兩兩比較的排序法。當數值範圍很小時，開一個「桶子」陣列 cnt，cnt[v] 記錄數值 v 出現幾次，再從小到大走訪桶子即得有序序列。時間 O(n + 範圍)。 / A non-comparison sort. When the value range is small, make a bucket array cnt where cnt[v] counts how many times value v appears, then sweep buckets from low to high to get sorted order. Runs in O(n + range).
桶 / Bucket：計數陣列裡的一格，對應一個可能的價格值。 / One slot in the counting array, corresponding to one possible price value.
整數溢位 / Integer overflow：當累加的數字超過 int 能表示的最大值（約 21 億）時會出錯。這裡用更大的型別避免。 / When an accumulated number exceeds the max an int can hold (~2.1 billion) it wraps around incorrectly. We use a wider type to avoid this.

思路

中文：最直覺的想法（暴力）是嘗試所有「買哪些冰淇淋」的組合，從中找出在預算內數量最多的一種。但 n 最大到 10^5，組合數是天文數字，完全不可行。我們需要找規律。關鍵觀察：要買「最多支」，每支冰淇淋對「數量」的貢獻都是 1，但花費不同——所以一塊錢花在便宜的冰淇淋上「更划算」。因此最佳策略是先買最便宜的，再買次便宜的，一直買到錢不夠為止；這就是貪心。為什麼貪心一定對？假設最優解沒有買某支很便宜的 A，卻買了某支較貴的 B，那把 B 換成 A 不會減少數量、還更省錢，所以「優先買便宜」永遠不會更差。要按價格由小到大處理，就需要排序。題目指定用計數排序：因為價格上限只有 10^5，我們開一個大小 10^5+1 的計數陣列 cnt，cnt[p] 記錄價格 p 的冰淇淋有幾支。然後從價格 1 掃到 10^5，對每個價格盡量多買：只要剩下的錢 coins 夠付一支該價格的冰淇淋，就買一支、扣錢、答案加一，直到該價格買完或錢不夠。錢不夠時就可以提前結束。

English: The brute-force idea is to try every subset of bars and pick the largest one within budget — but with n up to 10^5 the number of subsets is astronomical, so that's hopeless. Look for structure instead. The key insight: every bar adds exactly 1 to the count, but they cost different amounts, so a coin spent on a cheaper bar buys "more count per coin." The optimal strategy is therefore greedy: buy the cheapest bar, then the next cheapest, and so on until you run out of money. Why is greedy correct? If an optimal solution skipped a cheap bar A but included a pricier bar B, swapping B for A keeps the count the same and leaves more money — so preferring cheaper bars never hurts. To process prices in ascending order we must sort, and the problem mandates counting sort: since prices are at most 10^5, allocate a count array cnt of size 10^5+1 where cnt[p] is how many bars cost p. Then sweep prices from 1 upward; at each price buy as many as you can afford — while the remaining coins covers one bar of that price, subtract the price, increment the answer, and repeat — stopping early the moment money runs short.

逐步走查 / Walkthrough

Input: costs = [1,3,2,4,1], coins = 7

Step 1 — build counts / 建立計數陣列

price 價格	1	2	3	4
cnt 數量	2	1	1	1

(價格 1 出現兩次，其餘各一次 / price 1 appears twice, the rest once.)

Step 2 — sweep prices ascending, spend greedily / 由小到大掃描並貪心花費

start: coins = 7, bars = 0

price `p`	cnt[p]	能否買 affordable?	動作 action	coins after	bars after
1	2	7≥1 yes	買第1支 buy bar #1	6	1
1	(1 left)	6≥1 yes	買第2支 buy bar #2	5	2
2	1	5≥2 yes	買一支 buy one	3	3
3	1	3≥3 yes	買一支 buy one	0	4
4	1	0≥4 no	錢不夠，停止 stop	0	4

Result / 結果: bars = 4 ✓ 與預期相符 / matches expected output.

Solution — C

// 演算法 / Algorithm:
// 用計數排序統計每個價格出現幾次，再從最便宜的價格開始貪心地買，
// 只要錢夠就一直買，直到買不起為止。
// Counting-sort the prices, then greedily buy from the cheapest price up,
// purchasing as many as the remaining coins allow until we can't afford one.

#define MAX_COST 100000  // 價格上限 / the maximum possible price (per constraints)

int maxIceCream(int* costs, int costsSize, int coins) {
    // cnt[p] 將記錄價格剛好為 p 的冰淇淋有幾支
    // cnt[p] will hold how many bars cost exactly p.
    // 大小要 MAX_COST+1 因為索引從 0 用到 MAX_COST / size is MAX_COST+1 so index MAX_COST is valid.
    // 陣列初始化為全 0：{0} 會把第一個元素設 0，其餘自動補 0。
    // {0} zero-initializes the whole array (first element 0, the rest filled with 0).
    int cnt[MAX_COST + 1] = {0};

    // 第一遍：把每支冰淇淋丟進對應價格的「桶子」計數
    // First pass: drop each bar into the bucket for its price and count it.
    for (int i = 0; i < costsSize; i++) {
        cnt[costs[i]]++;  // costs[i] 是價格，當作索引；++ 表示該桶數量加一 / use the price as an index; ++ increments that bucket
    }

    int bars = 0;  // 已買的冰淇淋數量，也是最終答案 / number of bars bought so far = the answer

    // 第二遍：價格由小(1)到大(MAX_COST)掃描，先買便宜的
    // Second pass: sweep prices from cheapest (1) to most expensive, buying cheap first.
    for (int p = 1; p <= MAX_COST; p++) {
        // 對價格 p 的每一支冰淇淋，嘗試購買
        // For each bar that costs p, try to buy it.
        for (int k = 0; k < cnt[p]; k++) {
            if (coins < p) {
                // 連最便宜（當前 p）的都買不起，後面更貴的更不可能，直接回傳答案
                // Can't even afford price p; everything ahead is pricier, so we're done.
                return bars;
            }
            coins -= p;  // 付錢：剩餘硬幣減去這支的價格 / pay: subtract this bar's price from coins
            bars++;      // 成功買到一支 / one more bar bought
        }
    }

    // 走到這裡代表所有冰淇淋都買得起（錢有剩或剛好）
    // Reaching here means we could afford every bar.
    return bars;
}

Solution — C++

// 演算法 / Algorithm:
// 用計數排序統計每個價格的數量，再從最便宜的價格貪心購買，
// 只要剩餘硬幣足夠就繼續買，買不起時立即停止。
// Counting-sort prices into buckets, then greedily buy from the cheapest up,
// continuing while coins suffice and stopping as soon as one is unaffordable.

#include <vector>
using namespace std;

class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        const int MAX_COST = 100000;  // 價格上限 / maximum possible price per constraints

        // vector<int> 是會自動管理記憶體的動態陣列；這裡建立大小 MAX_COST+1、初值全 0 的計數桶。
        // vector<int> is a self-managing dynamic array; this makes MAX_COST+1 buckets all initialized to 0.
        vector<int> cnt(MAX_COST + 1, 0);

        // range-for：依序取出每個價格 c。加 & 取參考避免複製（雖然 int 很小，這是好習慣）。
        // Range-for iterates over each price c; '&' takes a reference to avoid copying (good habit).
        for (int c : costs) {
            cnt[c]++;  // 把這支冰淇淋計入對應價格的桶 / count this bar in the bucket for its price
        }

        int bars = 0;  // 已購買數量 = 答案 / bars bought so far = the answer

        // 由最便宜的價格往上掃描 / sweep from the cheapest price upward
        for (int p = 1; p <= MAX_COST; p++) {
            // 把價格 p 的冰淇淋一支支買下，直到買完或買不起
            // Buy the bars of price p one at a time until they're gone or unaffordable.
            while (cnt[p] > 0 && coins >= p) {
                coins -= p;  // 付款 / pay for this bar
                bars++;      // 數量加一 / one more bar
                cnt[p]--;    // 這個價格的庫存減一 / one fewer bar left at this price
            }
            // 若還有此價格的冰淇淋卻已買不起，後面更貴的也買不起，提前結束
            // If bars remain at price p but we can't afford them, all pricier ones are out of reach too.
            if (cnt[p] > 0) break;
        }

        return bars;  // 回傳買到的最大數量 / return the maximum number of bars
    }
};

複雜度 / Complexity

Time / 時間：O(n + M)，其中 n 是冰淇淋數量、M 是價格上限（10^5）。第一遍計數走訪所有 n 支是 O(n)；第二遍掃描桶子，外層走過 M 個價格，內層購買的總次數加起來最多就是 n 支，所以整體是 O(n + M)。計數排序的好處正是避開了比較排序的 O(n log n)。 / n = number of bars, M = max price (10^5). Counting is O(n); the sweep visits M buckets and performs at most n total buys, giving O(n + M). Counting sort beats comparison sort's O(n log n) here.
Space / 空間：O(M)，需要一個大小 M+1 的計數陣列。與輸入大小 n 無關，只取決於價格範圍。 / We need one count array of size M+1. This depends only on the price range, not on n.

Pitfalls & Edge Cases

整數溢位 / Overflow：很多解法會「先排序再累加前綴和」並把和存進 int；coins 最大 10^8、總和可能更大但仍在 int（約 2.1×10^9）邊緣，若不小心累加全部 10^5 支價格（最壞 10^10）就會溢位。本文的寫法逐支扣 coins 而非累加總和，coins 只會變小，永遠不溢位，是更安全的設計。 / Solutions that build a prefix sum can overflow a 32-bit int (a full sum can reach ~10^10). Our code subtracts from coins instead of summing, so the value only shrinks — no overflow.
提前停止 / Early termination：一旦遇到買不起的價格就必須停（C 用 return、C++ 用 break）。因為價格是由小到大掃描的，當前都買不起，後面只會更貴。少了這個判斷雖然不會出錯（後面 coins >= p 仍為假），但會白白多跑迴圈。 / Once a price is unaffordable, stop — prices ascend, so nothing later is cheaper. Omitting this still gives the right answer but wastes iterations.
計數陣列大小 / Array sizing：必須是 MAX_COST + 1，因為價格可達 10^5，而索引從 0 起算；少一格會造成越界寫入。 / The array must be MAX_COST + 1 long; price 10^5 is a valid index, and off-by-one here causes out-of-bounds writes.
一支都買不起 / Affording nothing（如範例 2）：最便宜的冰淇淋都比 coins 貴時，迴圈第一次就停，正確回傳 0。 / When even the cheapest bar exceeds coins (Example 2), the loop stops immediately and correctly returns 0.
重複價格 / Duplicate prices：同價格的多支會落進同一個桶，cnt[p] 自然記錄重數，內層迴圈逐一購買，不會漏算。 / Bars sharing a price land in the same bucket; cnt[p] records the multiplicity and the inner loop buys each one.