2144. Minimum Cost of Buying Candies With Discount

題目 / Problem

中文： 商店在打折賣糖果。每買兩顆糖果，就送第三顆免費。但有限制：你選來免費拿的那顆糖果，它的價格必須小於或等於你買的那兩顆糖果中較便宜的那顆。給你一個 0-indexed（從 0 開始編號）的整數陣列 cost，cost[i] 是第 i 顆糖果的價格，請回傳買下所有糖果的最小花費。

English: A shop sells candies at a discount: for every two candies you buy, you get a third candy free. The catch: the free candy's price must be ≤ the cheaper of the two candies you paid for. Given a 0-indexed integer array cost, where cost[i] is the price of the i-th candy, return the minimum total cost to buy all the candies.

Constraints / 限制： - 1 <= cost.length <= 100 - 1 <= cost[i] <= 100

Worked example / 範例： cost = [6,5,7,9,2,2] → 輸出 23。買 9 和 7，免費拿 6；買 5 和 2，免費拿剩下的 2。花費 = 9+7+5+2 = 23。

名詞解釋 / Glossary

• 貪心 / Greedy： 一種策略，每一步都做「當下看起來最好」的選擇，並且能證明這樣累積起來就是全域最優解。Make the locally-best choice at each step, which here provably yields the global optimum.
• 排序 / Sorting： 把陣列依大小重新排列。這裡我們從大到小排，好讓最貴的糖果排在前面。Rearranging the array by value; we sort descending so the most expensive candies come first.
• 降序 / Descending order： 由大到小排列（如 9,7,6,5,2,2）。From largest to smaller.
• qsort： C 標準函式庫的通用排序函式，需要你提供一個「比較函式」告訴它兩個元素誰大誰小。C's built-in sort; you pass it a comparison function.
• 比較函式 / Comparator： 一個小函式，回傳負數/零/正數來表示「a 排在 b 前/相等/後」。A small function returning negative/zero/positive to order two elements.
• 取餘數 % / Modulo： i % 3 取 i 除以 3 的餘數，用來每三個一組地找出第三顆。Gives the remainder; used to pick every third candy.

思路

先想最暴力的做法：我們想讓「免費」省下的錢越多越好，也就是讓被免費拿走的糖果價格總和最大。若枚舉所有「哪些糖果配成一組、哪一顆當免費」的組合，數量會爆炸，不可行。關鍵觀察在規則上：免費的那顆必須 ≤ 你買的兩顆中較便宜的一顆。換句話說，免費的糖果不能比你付錢的任一顆貴。那要怎麼讓免費的糖果盡量貴？答案是：先把最貴的兩顆拿來付錢，這樣第三貴的就能合法地被免費拿走（因為它一定 ≤ 那兩顆）。接著對剩下的糖果重複同樣的動作。把這個想法形式化，就是：把陣列從大到小排序，然後每三顆一組，付掉前兩顆、第三顆免費。也就是排序後，索引 0,1 付錢、2 免費；3,4 付錢、5 免費……凡是索引 i % 3 == 2 的糖果就是免費的，其餘都要加進總花費。最後不足三顆的尾巴（剩一或兩顆）就全部付錢，因為沒有「第三顆」可拿。這個貪心之所以正確，是因為每組裡免費掉的永遠是當前最大的可行候選，沒有任何其他配對能讓我們省下更多。

Start from brute force: we want to maximize the total price of the candies taken for free, since that's the money saved. Enumerating every way to pair candies and pick a free one blows up combinatorially. The key insight is the rule itself — the free candy must be ≤ the cheaper of the two you pay for, i.e. it can't be more expensive than either paid candy. So to make a free candy as expensive as possible, pay for the two most expensive candies first; then the third-most-expensive is automatically a legal free pick (it's ≤ both). Repeat on what's left. Formalized: sort descending, then in each group of three, pay for the first two and take the third free. After sorting, any candy at an index where i % 3 == 2 is free; everything else is added to the total. A leftover tail of one or two candies is fully paid for, since there's no third candy to grab. The greedy is correct because each group gives away the largest still-eligible candy, and no alternative pairing can save more.

逐步走查 / Walkthrough

以 cost = [1,2,3] 為例 / Using cost = [1,2,3]:

Step 1 — 降序排序 / Sort descending: [3, 2, 1]

結果 / Result: total = 5。買 3 和 2，免費拿 1，正好對上題目的唯一答案。Pay for 3 and 2, take 1 for free — matches the expected output of 5.

Solution — C

// 演算法：把價格從大到小排序，每三顆一組，付前兩顆、第三顆免費。
// Algorithm: sort prices descending; in each group of 3, pay the first two, the 3rd is free.
// 排序後索引 i 滿足 i % 3 == 2 的糖果免費，其餘累加。
// After sorting, candies at indices where i % 3 == 2 are free; sum up the rest.

#include <stdlib.h>  // 引入 qsort 所在的標頭檔 / header that provides qsort

// 比較函式：給 qsort 用，決定排序順序。
// Comparator: tells qsort how to order two elements.
// 回傳正數代表 a 該排在 b 後面，這裡讓「大的排前面」(降序)。
// Returning positive means a goes after b; here we put larger values first (descending).
static int cmpDesc(const void *a, const void *b) {
    // void* 是「不知道型別的指標」，先轉成 int* 再用 * 取出整數值。
    // void* is a type-less pointer; cast to int* then dereference (*) to read the int.
    int x = *(const int *)a;  // 取出第一個元素 / read the first element
    int y = *(const int *)b;  // 取出第二個元素 / read the second element
    return y - x;             // y - x 讓較大者排前面（降序）/ y - x sorts larger first (descending)
}

int minimumCost(int* cost, int costSize) {
    // 先就地把陣列由大到小排序 / sort the array in place, largest first.
    // 參數：陣列、元素個數、每個元素位元組數、比較函式。
    // Args: array, count, size of each element in bytes, comparator.
    qsort(cost, costSize, sizeof(int), cmpDesc);

    int total = 0;  // 累計要付的錢，初始為 0 / running sum of money we must pay, starts at 0.

    // 走過每一顆糖果 / iterate over every candy.
    for (int i = 0; i < costSize; i++) {
        // i % 3 == 2 表示這是每組的第三顆，免費，跳過不加錢。
        // i % 3 == 2 marks the 3rd candy of a group — it's free, so skip adding it.
        if (i % 3 == 2) {
            continue;  // 跳過本次迴圈剩下的部分 / skip the rest of this loop iteration.
        }
        total += cost[i];  // 其餘糖果都要付錢，累加價格 / all other candies are paid for.
    }

    return total;  // 回傳最小總花費 / return the minimum total cost.
}

Solution — C++

// 演算法：把價格由大到小排序，每三顆一組，付前兩顆、第三顆免費。
// Algorithm: sort prices descending; per group of 3, pay the first two and the 3rd is free.
// 排序後索引 i 滿足 i % 3 == 2 的糖果免費，其餘累加。
// After sorting, candies at indices where i % 3 == 2 are free; sum the rest.

#include <vector>     // 提供 std::vector 動態陣列 / provides std::vector (dynamic array)
#include <algorithm>  // 提供 std::sort / provides std::sort

class Solution {
public:
    int minimumCost(std::vector<int>& cost) {
        // std::sort 預設由小到大，傳第三個參數可自訂順序。
        // std::sort defaults to ascending; a 3rd argument customizes the order.
        // 這裡用 lambda（匿名小函式）讓較大者排前面（降序）。
        // Here a lambda (anonymous inline function) puts larger values first (descending).
        std::sort(cost.begin(), cost.end(), [](int a, int b) {
            return a > b;  // a 在 b 前 ⟺ a 較大 / a comes before b when a is larger
        });

        int total = 0;  // 累計要付的錢 / running total of money paid.

        // 用索引走訪，方便用 i % 3 判斷組內位置。
        // Index-based loop so we can test position-in-group with i % 3.
        for (int i = 0; i < static_cast<int>(cost.size()); i++) {
            // 每組第三顆（i % 3 == 2）免費，略過。
            // The 3rd candy of each group (i % 3 == 2) is free — skip it.
            if (i % 3 == 2) {
                continue;  // 不加錢，直接進下一輪 / add nothing, move to next iteration.
            }
            total += cost[i];  // 其餘糖果付錢 / pay for every other candy.
        }

        return total;  // 回傳最小總花費 / return the minimum total cost.
    }
};

複雜度 / Complexity

• Time: O(n log n) — 主要成本來自排序，n 是糖果數量；排序需要 O(n log n)，之後只走訪一遍是 O(n)，前者較大故總和為 O(n log n)。Sorting dominates (n = number of candies); the single O(n) pass afterward is smaller, so the total is O(n log n).
• Space: O(1) 或 O(log n) — 我們沒有額外開新陣列，只用了幾個變數；額外空間僅來自排序內部遞迴所需的堆疊，視實作而定。No extra array is allocated — just a few scalars; the only extra space is the sort's internal recursion stack, depending on the implementation.

Pitfalls & Edge Cases

• 排序方向 / Sort direction： 一定要降序。若忘了自訂比較函式而用預設升序，免費掉的會是便宜的糖果，省下的錢變少、答案偏大。Must sort descending; the default ascending order would give away cheap candies and overpay.
• i % 3 == 2 而非 == 0 / Off-by-one on the modulo： 免費的是每組的第三顆（索引 2,5,8…），不是第一顆。寫成 == 0 會免費掉最貴的糖果，違反規則且答案錯誤。The free one is the third in each group (indices 2,5,8…), not the first; == 0 would illegally free the most expensive candy.
• 尾端不足三顆 / Leftover tail < 3： 像 [5,5] 只剩兩顆、或只剩一顆時，沒有第三顆可免費，必須全部付錢。i % 3 == 2 的判斷天生就能處理——尾巴根本碰不到那個索引。Groups of one or two at the end have no free candy; the i % 3 == 2 check naturally handles this since the tail never hits that index.
• C 比較函式回傳值 / C comparator return value： qsort 看回傳值的正負號，不是布林。用 y - x 在本題安全（價格 1..100 不會溢位），但對任意大整數相減可能溢位，較穩健的寫法是用比較運算回傳 -1/0/1。qsort reads the sign of the return; y - x is safe here (values 1..100, no overflow) but could overflow for arbitrary ints — comparing and returning -1/0/1 is more robust in general.
• 無溢位風險 / No overflow on the sum： 最多 100 顆、每顆最多 100，總和 ≤ 10000，遠在 int 範圍內，不需用 long。At most 100×100 = 10000, comfortably within int.