2144-打折购买糖果的最小开销

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

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

• 比方说，总共有 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 <= cost.length <= 100
• 1 <= cost[i] <= 100

方法一：贪心

提示 1

我们采用如下的策略，可以使得购买糖果的总开销最小：

将糖果价格从高到低排序，然后按照每 3 个分成一组，花钱购买前两个，赠送第三个。

提示 1 解释

我们假设糖果数量为 n，那么最多可以赠送的糖果数量为 \lfloor n / 3 \rfloor，提示 1 的方法中，赠送糖果的数量与这个上界相等。那么，我们可以将证明分为两部分：

1. 开销最小的购买方案一定是赠送数量最多的方案；
2. 提示 1 的购买方案一定是赠送数量最多的方案中最优的。

对于第一部分，任意一个赠送糖果数量少于 \lfloor n / 3 \rfloor 的方案，都一定可以找到至少三个未被分组的糖果，对于这三个糖果，一定可以使得价格最低的糖果免费。因此命题 1 成立。

对于第二部分，我们不妨假设 cost 数组已经按照价格降序排序，根据定义，免费获得糖果中**价格最高的一定不大于 cost}[2]**（假设该下标存在，下同）。类似地，我们可以得出，价格第 k (0 \le k \le \lfloor n / 3 \rfloor) 高的糖果的价格一定不大于 cost}[3k+2]。

而提示 1 的方案中，所有的不等式均取了等号，同时考虑到免费糖果数量一定，因此命题 2 成立。

综上，我们可以得出，提示 1 的购买方案是开销最小的。

思路与算法

根据 提示 1，我们首先将糖果价格数组 cost 从高到低排序，此时免费获得所有下标模 3 余 2 的糖果的方案开销最小。随后我们遍历数组计算总开销，在计算时我们需要跳过这些免费获得的糖果。最终，我们将总开销返回作为答案。

代码

[sol1-C++]

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(), cost.end(), greater<int>());
        int res = 0;
        int n = cost.size();
        for (int i = 0; i < n; ++i) {
            if (i % 3 != 2) {
                res += cost[i];
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(key = lambda x: -x)
        res = 0
        n = len(cost)
        for i in range(n):
            if i % 3 != 2:
                res += cost[i]
        return res

复杂度分析

• 时间复杂度：O(n \log n)，其中 n 为 cost 的长度。即为对糖果按照价格排序的时间复杂度。

• 空间复杂度：O(\log n)，即为排序的栈空间开销。