考察的知识点:贪心;
解答方法分析:
- 初始化临时变量
temp
为起始资金w
。 - 创建一个存储成本和利润成对的向量
cows
。 - 创建一个优先队列
q
,用于存储利润。 - 获取利润和成本向量的长度,并保存在变量
n
中。 - 将成本和利润按照成本进行排序。
- 初始化变量
cur
为0。 - 循环
k
次,假设k
为指定的次数。 - 在当前的循环中,当
cur
小于n
并且当前成本cows[cur].first
小于等于现有资金w
时,将利润cows[cur].second
推入优先队列q
中,并将cur
增加1。 - 如果优先队列
q
不为空,则取出当前最大的利润值并将其加到现有资金w
中,并将其从优先队列中移出。 - 如果优先队列
q
为空,则跳出循环。 - 返回最终的资金差额
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; } };