双周赛第70场:LeetCode:5971.打折购买糖果的最小开销

浏览次数 : 次 2022-01-23

博文字数统计 : 665字 | 阅读所需时长 : 2分

× 文章目录

1. 双周赛第70场：LeetCode：5971.打折购买糖果的最小开销
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法：贪心 & 排序

双周赛第70场：LeetCode：5971.打折购买糖果的最小开销
- 时间：2022-01-22
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组
- 算法：贪心

双周赛第70场：LeetCode：5971.打折购买糖果的最小开销

1. 题目描述

题目：原题链接
- 一家商店正在打折销售糖果。每购买两个糖果，商店会免费送一个糖果。
- 免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的较小值。
- 比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
- 给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得所有糖果的最小总开销。
输入输出规范
- 输入：价格数组 cost
- 输出：整型，表示最小花费
输入输出示例
- 输入：cost = [6,5,7,9,2,2]
- 输出：23

2. 方法：贪心 & 排序

思路
- 本题要计算购买所有物品的最小开销，且可以买二赠一，但是赠送的一定比买的这两个便宜
- 根据贪心的思想，我们每次可以选择买最贵的两个物品，然后赠送第三贵的物品，然后再从剩余的物品中重复这一操作，剩余物品不足两个时直接购买，最后得到的就是最小开销
- 那么，虽然解题思路非常容易理解，但是如何证明这样贪心求解一定是最优解呢
- 简单通过反证法来证明：如果每次购买的不是最贵的两个，而是任意两个物品，这里假设买了第二和第三贵的物品，那么获赠的只能是第四贵及以下的物品，最贵的物品仍然必须购买，那么，局部花费为：cost[1]+cost[2]+cost[3]，而贪心求解的结果为买第一、第二、第四贵：cost[1]+cost[2]+cost[4]，花费更小

题解：排序并模拟

public int minimumCost(int[] cost) {
       if(cost == null || cost.length == 0) return 0;
       int n = cost.length;
       if(n == 1) return cost[0];
       if(n == 2) return cost[0] + cost[1];
       int minCost = 0;
       Arrays.sort(cost);
       for(int i = n-1; i>=0; i--) {
           minCost += cost[i];
           if(i - 1 >= 0)  minCost += cost[i - 1];
           i-=2;
       }
       return minCost;
   }

复杂度分析：n 是数组的长度
- 时间复杂度：$O(nlog)$，受限于排序的复杂度
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-23 20:20:21
最后更新： 2022-02-20 13:34:08
本文标题： 双周赛第70场:LeetCode:5971.打折购买糖果的最小开销
本文链接： https://chthollists.github.io/post/83a2cdaa.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！