題目

一家商店正在打折銷售糖果。每購買 兩個(gè) 糖果，商店會(huì) 免費(fèi) 送一個(gè)糖果。
免費(fèi)送的糖果唯一的限制是：它的價(jià)格需要小于等于購買的兩個(gè)糖果價(jià)格的 較小值 。
比方說，總共有 4 個(gè)糖果，價(jià)格分別為 1 ，2 ，3 和 4 ，一位顧客買了價(jià)格為 2 和 3 的糖果，那么他可以免費(fèi)獲得價(jià)格為 1 的糖果，但不能獲得價(jià)格為 4 的糖果。
給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 cost ，其中 cost[i] 表示第 i 個(gè)糖果的價(jià)格，請你返回獲得 所有 糖果的 最小 總開銷。
示例 1：
輸入：cost = [1,2,3]
輸出：5
解釋：我們購買價(jià)格為 2 和 3 的糖果，然后免費(fèi)獲得價(jià)格為 1 的糖果。
總開銷為 2 + 3 = 5 。這是開銷最小的 唯一 方案。
注意，我們不能購買價(jià)格為 1 和 3 的糖果，并免費(fèi)獲得價(jià)格為 2 的糖果。
這是因?yàn)槊赓M(fèi)糖果的價(jià)格必須小于等于購買的 2 個(gè)糖果價(jià)格的較小值。
示例 2：
輸入：cost = [6,5,7,9,2,2]
輸出：23
解釋：最小總開銷購買糖果方案為：

• 購買價(jià)格為 9 和 7 的糖果
• 免費(fèi)獲得價(jià)格為 6 的糖果
• 購買價(jià)格為 5 和 2 的糖果
• 免費(fèi)獲得價(jià)格為 2 的最后一個(gè)糖果
  因此，最小總開銷為 9 + 7 + 5 + 2 = 23 。
  示例 3：
  輸入：cost = [5,5]
  輸出：10
  解釋：由于只有 2 個(gè)糖果，我們需要將它們都購買，而且沒有免費(fèi)糖果。
  所以總最小開銷為 5 + 5 = 10 。
  提示：
  1 <= cost.length <= 100
  1 <= cost[i] <= 100
  來源：力扣（LeetCode）

解題思路

??對于給定的cost，最大值和第二大的值肯定不會(huì)被贈(zèng)送，那么第三大值如果存在肯定會(huì)被贈(zèng)送，所以可以將cost按從大到小的順序進(jìn)行排序，然后取出前三大的值進(jìn)行操作，剩下的子序列便是又一輪的操作。

class Solution:def minimumCost(self, cost: List[int]) -> int:s=0cost.sort(reverse=True)for i in range(len(cost)):if (i+1)%3!=0:  #第三大的值不需要計(jì)入總價(jià)s+=cost[i]return s

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之打折购买糖果的最小开销的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。