E2144.打折购买糖果的最小开销

greedy, https://leetcode.cn/problems/minimum-cost-of-buying-candies-with-discount/

一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。

免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。

• 比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。

给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。

示例 1：

输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。

示例 2：

输入：cost = [6,5,7,9,2,2]
输出：23
解释：最小总开销购买糖果方案为：
- 购买价格为 9 和 7 的糖果
- 免费获得价格为 6 的糖果
- 购买价格为 5 和 2 的糖果
- 免费获得价格为 2 的最后一个糖果
因此，最小总开销为 9 + 7 + 5 + 2 = 23 。

示例 3：

输入：cost = [5,5]
输出：10
解释：由于只有 2 个糖果，我们需要将它们都购买，而且没有免费糖果。
所以总最小开销为 5 + 5 = 10 。

为了求得购买所有糖果的最小总开销，我们可以采用贪心算法。

思路分析

为了让总开销最小，我们应当尽可能让价格高的糖果作为“免费赠送”的糖果。 根据规则，每购买两个糖果，可以免费获得一个价格小于等于这两个糖果价格较小值的糖果。

1. 排序：我们将糖果价格从大到小（降序）进行排序。
2. 分组：从最贵的糖果开始，每三个糖果分成一组。例如对于排序后的数组：[c1, c2, c3, c4, c5, c6, ...]（满足 $c_1\ge c_2\ge c_3\ge \dots$）。
   • 第一组：c1 和 c2 购买，c3 免费送（因为 $c_3\le c_2\le c_1$）。
   • 第二组：c4 和 c5 购买，c6 免费送（因为 $c_6\le c_5\le c_4$）。
   • 依此类推。
3. 统计开销：在遍历排序后的数组时，下标（从0开始）满足 (i + 1) % 3 == 0 的糖果可以免费获得，其余的糖果需要自费购买。

这种贪心策略能够确保我们每次都将当前最贵的两个糖果搭配，从而免单第三贵的糖果，使得免费糖果的总价值达到最大，进而使总开销达到最小。

Python 代码实现

from typing import List

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        # 将糖果价格从大到小排序
        cost.sort(reverse=True)
        
        total_cost = 0
        for i in range(len(cost)):
            # 每 3 个糖果中的第 3 个（下标为 2, 5, 8...）是免费的，不需要累加
            if (i + 1) % 3 != 0:
                total_cost += cost[i]
                
        return total_cost

复杂度分析

• 时间复杂度：$O(N\log N)$，其中 $N$ 为糖果的数量。主要的时间开销在于对价格数组进行排序。
• 空间复杂度：$O(1)$ 或 $O(N)$，具体取决于排序算法的实现（Python 的 sort 方法使用的是 Timsort，空间复杂度为 $O(N)$）。