题解 | #最大养牛利润# 贪心

知识点

贪心 堆

思路

我们按照cost的大小进行排序，每一次饲养可以选取当前cost允许养的利润最大的牛。实现上我们用一个指针来维护一下加入的位置，用一个堆来选每次最大利润的牛。一共进行k轮，k不大于n。

时间复杂度为

AC Code（C++）

#include <numeric>
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param w int整型 
     * @param profits int整型vector 
     * @param costs int整型vector 
     * @return int整型
     */
    using pii = pair<int, int>;
    int findMaximizedProfits(int k, int w, vector<int>& profits, vector<int>& costs) {
        // 每一次找成本可以接受的最大利润的养
        int n = profits.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int x, int y) {
            return costs[x] < costs[y];
        });
        priority_queue<int> q;

        k = min(n, k);
        int idx = 0, res = w;
        while (k --) {
            while (idx < n and costs[id[idx]] <= res) {
                auto t = id[idx ++];
                q.emplace(profits[t]);
            }
            if (q.empty()) break;
            res += q.top();
            q.pop();
        }
        return res - w;
    }
};