打折购买糖果的最小开销

难度: Easy

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

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

比方说，总共有 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

Submission

运行时间: 23 ms

内存: 16.1 MB

from typing import List

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)  # 按照价格降序排列
        total_cost = 0
        i = 0
        
        while i < len(cost):
            if i + 1 < len(cost):
                # 每次选择两个价格最高的糖果进行购买，并免费获得一个价格较低的糖果
                total_cost += cost[i] + cost[i+1]
                i += 3
            else:
                # 如果只剩下一个糖果，则直接购买
                total_cost += cost[i]
                i += 1
        
        return total_cost

Explain

该题解的策略是首先将糖果按价格从高到低排序，以保证在购买时能够优先获取价格较高的糖果，从而使得在每次购买两个糖果时，能够免费获得价格相对较低的糖果。具体实施中，每次循环选取三个糖果（如果存在），购买最贵的两个，并免费获得第三个。如果剩下的糖果不足三个，直接购买剩余的糖果。这样做的目的是最大化每次免费获得糖果的价值。

时间复杂度: O(n log n)

空间复杂度: O(1)

from typing import List

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost.sort(reverse=True)  # 按照价格降序排列
        total_cost = 0  # 初始化总开销
        i = 0  # 初始化索引
        
        while i < len(cost):  # 遍历所有糖果
            if i + 1 < len(cost):  # 如果当前位置后还有至少两个糖果
                total_cost += cost[i] + cost[i+1]  # 购买这两个糖果
                i += 3  # 跳过免费的第三个糖果
            else:
                total_cost += cost[i]  # 只剩一个糖果时，直接购买
                i += 1
        return total_cost  # 返回计算的总开销

Explore

按照价格从高到低排序的目的是在每次购买操作中最大化节省。由于规则允许每买两个糖果免费获得一个，通过优先购买最贵的糖果，可以确保每次免费获得的糖果是当前可选糖果中价格相对较低的。这种策略确保了总支付金额最小化，因为它减少了高价值糖果的支付次数，并最大化了低价值糖果的免费获得次数。

在剩下两个糖果的情况下，算法并没有涉及选择问题，因为只有两个糖果可供选择，所以必须购买这两个糖果，没有免费获得的糖果。这种情况下，策略简单地涉及支付这两个糖果的总价，而没有进一步的优化空间。

在这个策略中，选择最贵的两个糖果并跳过第三个作为免费糖果是最优的决策。这样做是因为我们希望支付最贵的糖果，从而最大化免费获得的糖果的价值。如果选择较便宜的糖果作为付费糖果，那么免费获得的糖果平均价格会更高，从而增加总花费。因此，在这种情况下，没有更好的选择。

如果数组长度不是3的倍数，处理剩下的一到两个糖果的逻辑是直接购买这些糖果，因为没有足够的糖果来组成一个完整的买二送一的组合。这种处理方式是高效的，因为它简单且直接，确保了所有糖果都被考虑到，同时避免了复杂的额外逻辑或不必要的计算。