給出一列數,一共可以實施k個操作,每次可以將其中一個數減去floor(piles[i] / 2),問k次操作之后剩下的數字和最小是多少
思路:用優先隊列保存經過x次操作之后的數字,用python的heapq寫起來就很方便,每次操作直接用heapreplace把heap頂的數減半替代原值即可(比先pop,改值之后再push要快,beat 100%)
因為heapq是最小堆,所以建堆時先將所有數取負
1 #2279
2 #Runtime: 3519 ms (Beats 100%)
3 #Memory: 26 MB (Beats 37.21%)
4
5 class Solution(object):
6 def minStoneSum(self, piles, k):
7 """
8 :type piles: List[int]
9 :type k: int
10 :rtype: int
11 """
12 hq = [-x for x in piles]
13 heapify(hq)
14 for _ in range(k):
15 heapreplace(hq, hq[0] // 2)
16 return -sum(hq)