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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

贪心算法、双指针

题目解答方法的文字分析

这道题目可以使用贪心算法和双指针来解决。我们可以将A牛的价格和B牛的价格两两组合，并计算每对牛的总价格。然后，我们可以使用一个优先队列（最小堆）来维护当前总价格最大的k对牛。在遍历过程中，我们使用两个指针i和j来分别指向A牛的价格数组和B牛的价格数组，不断选择当前总价格最大的牛对，并将其加入优先队列。当优先队列中的牛对达到k个时，我们可以将当前最小的牛对替换掉，以保持优先队列中总价格最大的k对牛。

具体步骤如下：

1. 初始化一个优先队列minHeap，用于维护当前总价格最大的k对牛。将A牛的价格和B牛的价格两两组合，并计算每对牛的总价格，然后将其加入minHeap（按总价格升序排序）。
2. 初始化一个空vector res，用于存储最终结果。
3. 使用两个指针i和j分别指向A牛的价格数组和B牛的价格数组，并设置一个变量count为0，用于记录已经选择了多少对牛。
4. 从minHeap中选择当前总价格最大的牛对，并将其加入res，同时将count加一。
5. 如果count达到了k，结束遍历。
6. 继续选择下一个总价格最大的牛对，并重复步骤4和步骤5，直到minHeap为空或者count达到了k。
7. 返回res，表示最大的k对牛的售价。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pricesA int整型vector 
     * @param pricesB int整型vector 
     * @param k int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> kPairsWithLargestSums(vector<int>& pricesA, vector<int>& pricesB, int k) {
        int m = pricesA.size();
        int n = pricesB.size();
        vector<vector<int>> res;
        priority_queue<pair<int, pair<int, int>>> minHeap; // 维护当前总价格最大的k对牛（最小堆）

        // 将A牛的价格和B牛的价格两两组合，并计算每对牛的总价格，然后将其加入minHeap（按总价格升序排序）
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                minHeap.push(make_pair(pricesA[i] + pricesB[j], make_pair(pricesA[i], pricesB[j])));
            }
        }

        // 从minHeap中选择当前总价格最大的牛对，并将其加入res
        int count = 0;
        while (!minHeap.empty() && count < k) {
            auto top = minHeap.top();
            minHeap.pop();
            int priceA = top.second.first;
            int priceB = top.second.second;
            res.push_back({priceA, priceB});
            count++;
        }

        return res;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！