5971. 打折购买糖果的最小开销

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 135 阅读 / 724 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

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

比方说,总共有 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 个糖果价格的较小值。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-cost-of-buying-candies-with-discount
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

从大到小排序,每三个购买前两个

代码:

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

评论区