// 演算法 / 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
    }
};