知识点
贪心 堆
思路
我们按照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; } };