题解 | #最高售价的两只牛#

• 题目考察的知识点 : 贪心算法
• 题目解答方法的文字分析：

1. 创建一个最小堆 minHeap，用于存储每个牛对的负总价值，并保持它们按照降序排列。因为 Python 的默认是最小堆，所以在加入时将其取负号。
2. 对于列表 pricesA 中的每个元素和列表 pricesB 中的每个元素进行组合，并计算其总价值。将每个牛对和其总价值添加到最小堆 minHeap 中。因为我们要找到最大利润的前 k 对牛，所以在插入最小堆时可以用负数代替正数。
3. 从 minHeap 中弹出当前总价值最大的前 k 对牛，并将它们添加到结果列表 res 中。由于 minHeap 中保存的是负数，因此在弹出元素时需要先将它们取负号

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pricesA int整型一维数组
# @param pricesB int整型一维数组
# @param k int整型
# @return int整型二维数组
#
import heapq
class Solution:
    def kPairsWithLargestSums(
        self, pricesA: List[int], pricesB: List[int], k: int
    ) -> List[List[int]]:
        m, n = len(pricesA), len(pricesB)
        minHeap = [] # 维护当前总价格最大的k对牛（最小堆）

        # 将A牛的价格和B牛的价格两两组合，并计算每对牛的总价格，然后将其加入minHeap（按总价格升序排序）
        for i in range(m):
            for j in range(n):
                heapq.heappush(minHeap, (-(pricesA[i] + pricesB[j]), -pricesA[i], -pricesB[j]))

        # 从minHeap中选择当前总价格最大的牛对，并将其加入res
        res = []
        count = 0
        while minHeap and count < k:
            _, priceA, priceB = heapq.heappop(minHeap)
            res.append([-priceA, -priceB])
            count += 1

        return res