网站建设公司的正反,免费wordpress申请,制作app的免费软件,淮安市工程造价信息网文章目录1. 题目2. 解题1. 题目
一家商店正在打折销售糖果。每购买 两个 糖果#xff0c;商店会 免费 送一个糖果。
免费送的糖果唯一的限制是#xff1a;它的价格需要小于等于购买的两个糖果价格的 较小值 。
比方说#xff0c;总共有 4 个糖果#xff0c;价格分别为 1…
文章目录1. 题目2. 解题1. 题目
一家商店正在打折销售糖果。每购买 两个 糖果商店会 免费 送一个糖果。
免费送的糖果唯一的限制是它的价格需要小于等于购买的两个糖果价格的 较小值 。
比方说总共有 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-cost-of-buying-candies-with-discount 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
假设 abcda b c dabcdabd−(acb)d−c0abd-(acb) d-c 0abd−(acb)d−c0所有买最大的两个免费获取第三大的剩余的依次类推是最优的方法
class Solution {
public:int minimumCost(vectorint cost) {// a b c d// abd-(acb) 0sort(cost.rbegin(), cost.rend());int ans 0, n cost.size();for(int i 0; i n; i3){ans cost[i];if(i1 n)ans cost[i1];}return ans;}
};8 ms 10.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
