考察的知识点:贪心;

解答方法分析:

  1. 初始化临时变量temp为起始资金w
  2. 创建一个存储成本和利润成对的向量cows
  3. 创建一个优先队列q,用于存储利润。
  4. 获取利润和成本向量的长度,并保存在变量n中。
  5. 将成本和利润按照成本进行排序。
  6. 初始化变量cur为0。
  7. 循环k次,假设k为指定的次数。
  8. 在当前的循环中,当cur小于n并且当前成本cows[cur].first小于等于现有资金w时,将利润cows[cur].second推入优先队列q中,并将cur增加1。
  9. 如果优先队列q不为空,则取出当前最大的利润值并将其加到现有资金w中,并将其从优先队列中移出。
  10. 如果优先队列q为空,则跳出循环。
  11. 返回最终的资金差额w - temp,即最大化的利润。

所用编程语言: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 temp = w;
        vector<pair<int, int>> cows;
        priority_queue<int> q;
        int n = profits.size();
        for (int i = 0; i < n; ++i) {
            cows.push_back({costs[i], profits[i]});
        }
        sort(cows.begin(), cows.end());
        int cur = 0;
        for (int i = 0; i < k; ++i) {
            while (cur < n && cows[cur].first <= w) {
                q.push(cows[cur].second);
                cur++;
            }
            if (!q.empty()) {
                w += q.top();
                q.pop();
            } else {
                break;
            }
        }
        return w - temp;
    }
};