Re: [閒聊] 每日LeetCode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 1962. Remove Stones to Minimize the Total
: 給你一堆石頭，你每次可以從其中一堆移除floor(piles[i] / 2)個石頭，求出做了
: n次操作後，這堆石頭最少還剩下幾個石頭。
: Example:
: Input: piles = [5,4,9], k = 2
: Output: 12
: Explanation:
: 移除 piles[2]，piles = [5,4,5]
: 移除 pile[0]或piles[2]，piles = [3,4,5] or [5,4,3]
思考：
每次都要拿最多石頭起來 -> Greedy
每次都要找到最多的那堆 -> 排序
詳細作法：
先把 piles 由大到小排序（say data），每次都在 data[0] 拿石頭並維持順序
而既然我們的 data 已經排好了，我們可以一個一個往後比，直到找到比處理完
的石頭堆還小的地方，塞進去就可以
Code：
class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
data = piles[:]
data.sort(reverse=True)
while k > 0:
k -= 1
data[0] -= floor(data[0] / 2)
for i in range(1, len(data)):
if data[i - 1] < data[i]:
data[i - 1], data[i] = data[i], data[i - 1]
else:
break
return sum(data)
結果：
豪不意外的 TLE 了 (。・ω・。)
最佳化：
我不自己刻啦！JOJO
from sortedcontainers import SortedList
class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
data = SortedList(piles, key=lambda x: -x)
while k > 0:
k -= 1
data.add(ceil(data.pop(0) / 2))
return sum(data)
搞定。
結語：
Official solution 也是直接用 heapq 做
這樣的題目真的有 Medium 嗎 = =?
--
僕の妹がこんなに可愛いわけがない担当のアユニ‧D です
https://i.imgur.com/Zvo15mG.jpg
https://twitter.com/AYUNiD_BiSH
https://instagram.com/ayunid_official
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.230.129 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672247774.A.7FE.html
推
12/29 01:39,
2年前
, 1F
12/29 01:39, 1F
推
12/29 15:13,
2年前
, 2F
12/29 15:13, 2F
→
12/29 15:13,
2年前
, 3F
12/29 15:13, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 159 之 719 篇)：