## 前言
* **大家好**，我是新人简书博主：「 [个人主页](https://www.jianshu.com/u/8000305d22b9)」主要分享程序员生活、编程技术、* * 以及每日的LeetCode刷题记录，欢迎大家关注我，一起学习交流，谢谢！
* 正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
* 同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「[GitHub](https://github.com/Chthollists/LeetCodeRecord)」上面 ~
* 今天是坚持写题解的33天(haha，从21年圣诞节开始的)，大家一起加油
---
* 双周赛第70场：LeetCode：5971.打折购买糖果的最小开销
* 时间：2022-01-22
* 力扣难度：Easy
* 个人难度：Easy
* 数据结构：数组
* 算法：贪心
---
# 双周赛第70场：LeetCode：5971.打折购买糖果的最小开销
## 1. 题目描述
* 题目：[原题链接](https://leetcode-cn.com/problems/minimum-cost-of-buying-candies-with-discount/)
* 一家商店正在打折销售糖果。每购买两个糖果，商店会免费送一个糖果。
* 免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的较小值 。
* 比方说，总共有 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]，花费更小
* 题解：排序并模拟
> ```java
> 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)$
---
## 最后
如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！
* 「[个人博客](https://chthollists.github.io/)」
* 「[掘金](https://juejin.cn/user/26854211457719)」
* 「[LeetCode](https://leetcode-cn.com/u/chthollists/)」
