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

题目考察的知识点

这道题目考察的是贪心算法、优先队列（堆）的运用以及数组的遍历。

题目解答方法的文字分析

题目给出了一个数组 profits，表示每头牛的利润，和一个数组 costs，表示每头牛的饲养成本。农民们初始资本为 w，并且最多只能饲养 k 头牛。我们需要设计一个饲养计划，使得农民们最终获得的最大利润最多。

我们可以使用贪心算法来解决这个问题。首先，我们将 profits 和 costs 数组中的牛按照利润从大到小进行排序，并将其存储在一个数组 pairs 中。然后使用一个优先队列（最大堆）来存储当前可选的牛的饲养成本。接着，遍历 pairs 数组，对于每头牛，判断当前资本是否足够饲养该牛。如果足够饲养，将该牛的利润加到总利润上，并将该牛的饲养成本加入优先队列中，然后更新资本 w。如果不足够饲养，说明当前最大的利润已经不能再选，退出循环。继续遍历下一个牛，直到遍历完所有的牛或者选满了 k 头牛。

例子展示：假设 k = 2，w = 10，profits = [6, 3, 4]，costs = [2, 2, 2]。

  1. 将 profits 和 costs 数组中的牛按照利润从大到小进行排序，得到 pairs 数组：pairs = [(6, 2), (4, 2), (3, 2)]。
  2. 用pairs初始化最大堆 maxHeap，并将 totalProfit用w = 10 初始化。
  3. 遍历 pairs 数组：对于第一头牛 (6, 2)，资本足够饲养，不行，利润加到总利润上，totalProfit = 10 + 6 = 16，对于第二头牛 (4, 2)，资本足够饲养，利润加到总利润上，totalProfit = 16 + 4 = 20，
  4. 继续遍历下一头牛，但 k = 2，已经选满了，结束遍历。

最终 totalProfit = 20，再减去w=10 表示农民们最多可以获得的利润为 10。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param w int整型 
     * @param profits int整型vector 
     * @param costs int整型vector 
     * @return int整型
     */
    int findMaximizedProfits(int k, int w, vector<int>& profits, vector<int>& costs) {
        int n = profits.size();
        vector<pair<int, int>> pairs; // 存储每头牛的利润和饲养成本
        for (int i = 0; i < n; ++i) {
            pairs.push_back({profits[i], costs[i]});
        }
        sort(pairs.begin(), pairs.end(), greater<pair<int, int>>()); // 按照利润从大到小排序

        priority_queue<int> maxHeap; // 最大堆，存储当前可选的牛的饲养成本
        for (int i = 0; i < n; ++i) {
            maxHeap.push(pairs[i].second);
        }

        vector<bool> chosen(n, false); // 标记数组，记录每头牛是否被选择过饲养
        int totalProfit = w; // 总利润，初始值为初始资本 w
        for (int i = 0; i < k; ++i) {
            int maxProfit = 0;
            int chosenCow = -1;
            for (int j = 0; j < n; ++j) {
                if (!chosen[j] && pairs[j].second <= totalProfit) {
                    // 如果该牛没有被选择过饲养，并且当前资本足够饲养该牛
                    if (pairs[j].first > maxProfit) {
                        // 更新最大利润和被选择的牛的索引
                        maxProfit = pairs[j].first;
                        chosenCow = j;
                    }
                }
            }
            if (chosenCow == -1) {
                // 如果没有可选的牛，说明已经选满了 k 头牛，退出循环
                break;
            }
            chosen[chosenCow] = true; // 将该牛标记为已被选择
            totalProfit += maxProfit; // 将该牛的利润加到总利润上
        }

        return totalProfit-w;//输出不包括初始资本
    }
};

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