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：

输入：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. 每买两颗糖果可以免费获得一颗，且免费糖果的成本不能超过购买的两颗糖果中成本较小的那颗
  2. 为了最大化免费糖果的价值，我们应该优先购买成本较高的糖果，这样能免费获得更多价值的糖果

贪心策略：

  • 将糖果按成本从高到低排序
  • 每三颗糖果为一组，购买前两颗（成本最高的两颗），第三颗免费获得
  • 这样既满足了免费糖果成本不超过购买糖果最小成本的条件，又最大化了免费糖果的价值

算法步骤：

  1. 对成本数组进行降序排序
  2. 按每三个一组遍历，每组只需要支付前两个的成本
  3. 如果最后不足三个，则全部购买

这种方法保证了我们总是用最高成本的糖果去"换取"免费的糖果，从而达到最小总成本。

时间复杂度主要由排序决定，为O(n log n)。

代码实现

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

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

public class Solution {
    public int MinimumCost(int[] cost) {
        Array.Sort(cost, (a, b) => b.CompareTo(a));
        
        int total = 0;
        for (int i = 0; i < cost.Length; i++) {
            if (i % 3 != 2) {
                total += cost[i];
            }
        }
        
        return total;
    }
}

/**
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(cost) {
    cost.sort((a, b) => b - a);
    
    let total = 0;
    for (let i = 0; i < cost.length; i++) {
        if (i % 3 !== 2) {
            total += cost[i];
        }
    }
    
    return total;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
贪心算法O(n log n)O(1)

说明：

  • 时间复杂度：O(n log n)，主要由排序操作决定
  • 空间复杂度：O(1)，只使用常量额外空间（原地排序）

相关题目