2931. 购买物品的最大开销（Rating 1822）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

2931. 购买物品的最大开销

Rating 1819

思路

因为排序了，所以我们能买到每个商店的最小价值商品

因为我们可以任意选择商店，那么我们能买到所有剩余商品中的最小价值商品

因此我们维护一个m长度的小顶堆，从小往大买即可。

或者倒过来从前面开始买，维护一个m长度的大顶堆，从大往小买也可。

代码

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        m, n = len(values), len(values[0])
        d = m * n
        hq = [(-values[i][0], i, 0) for i in range(m)] # 取负号变成大顶堆
        heapq.heapify(hq)
        ret = 0
        while hq:
            v, i, j = heapq.heappop(hq)
            ret -= d * v
            d -= 1
            if j + 1 < n:
                heapq.heappush(hq, (-values[i][j + 1], i, j + 1))
        return ret