ETH官方钱包

前往
大廳
主題

LeetCode - 2144. Minimum Cost of Buying Candies With Discount 解題心得

Not In My Back Yard | 2022-08-26 12:00:23 | 巴幣 0 | 人氣 199

題目連結:


題目意譯:
一間糖果店正在促銷。現在每買兩顆糖果,店家就會再免費送一顆。

顧客們可以選擇任意的糖果作為免費的贈品,只要該顆糖果的價格小於等於兩個剛購買的糖果中的價格最小值即可。

例如,如果現在有 4 顆糖果各自價格為 1 、 2 、 3 和 4,而且顧客買了價格 2 和 3 的糖果,則他們可以把價格 1 的糖果免費帶走,但是價格 4 的則不行。

給定一個索引值從 0 開始的整數陣列 cost,其中 cost[i] 代表著第 i 顆糖果的價格,回傳買下所有糖果最少所需的花費金額。

限制:
1 ≦ cost.length ≦ 100
1 ≦ cost[i] ≦ 100



範例測資:
範例 1:
輸入: cost = [1,2,3]
輸出: 5
解釋: 我們買入價格 2 和 3 的糖果,並拿走價格 1 的糖果作為贈品。
買下所有糖果的總花費為 2 + 3 = 5。而這也是唯一一個我們可以購買這些糖果的方式。
注意到我們不能買下價格 1 和 3 的糖果,然後免費拿走價格 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。


解題思維:
由於可以拿的附贈糖果是取決於先前買的兩顆糖果之價格最小值,因此我們可以看到最貴的糖果基本上只能用買的(除非該價格的糖果有三顆以上(含))。因此我們將所有糖果按照價格排序(高到低),然後每兩顆就用買的、而第三顆就是用送的(寫成程式就是單純地跳過這顆糖果)。

然後將過程中是用「買」的糖果之價格加總起來即是所求最小花費。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作