题目描述

官方描述(中文)
2021/09/08每日一题

思路

贪心+优先队列

  1. 先将启动资本与纯利润建立联系,使用pair建立,first是启动资本,second是纯利润。
  2. 对建立好的联系数组进行由小到大排序
  3. 遍历排序好的数组,只要是以当前资本可以启动的项目,都先将纯利润放入优先队列(大根堆)中。
  4. 遍历完成之后将队列的第一个元素既以当前资本可以获得的最大利润与当前资本相加,得到新的初始资本。
  5. 重复上述3,4步骤k次。

代码

class Solution {
public:
	int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) 
	{
		vector<std::pair<int, int>>vecNums;
		priority_queue<int, vector<int>, less<int>>queNums;
		for (int i = 0; i < profits.size(); ++i)
		{
			vecNums.push_back({ capital[i], profits[i] });
		}
		sort(vecNums.begin(), vecNums.end());
		int currPos{ 0 };
		while (k--)
		{
			while (currPos < profits.size() && vecNums[currPos].first <= w)
			{
				queNums.push(vecNums[currPos].second);
				++currPos;
			}
			if (!queNums.empty())
			{
				w += queNums.top();
				queNums.pop();
			}
		}
		return w;
	}
};

执行结果

image.png

Q.E.D.