↓Skip to main content
  1. Posts/

LeetCode-2551 将珠子放入背包中

·1 min·
Table of Contents

LeetCode-2551 将珠子放入背包中 #

Solution 1 #

注意到分组等价于放隔板, 每个隔板可以获得两侧的分数. 贪心地选出分数最高和最低的 $k - 1$ 个隔板即可.

代码如下:

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        pq1, pq2 = [], []
        for i in range(1, len(weights)):
            heappush(pq1, - weights[i] - weights[i - 1])
            heappush(pq2, weights[i] + weights[i - 1])
            if len(pq1) == k:
                heappop(pq1)
                heappop(pq2)
        return sum(pq1 + pq2)