【贪心堆优先队列】502. IPO

本文涉及知识点

贪心堆优先队列

LeetCode502. IPO

假设力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
提示：
1 <= k <= 10⁵
0 <= w <= 10⁹
n == profits.length
n == capital.length
1 <= n <= 10⁵
0 <= profits[i] <= 10⁴
0 <= capital[i] <= 10⁹

贪心

第i个项目显然是满足最小资本纯利最大的项目。纯利不会为负数，也就是不会亏损。
用大根堆保持能够完成的项目，第i个项目就是最是堆顶元素。
如果堆顶为空，则提前结束。
注意：capital 没有排序，对其下标排序。或放到多键有序映射或堆中。

代码

核心代码

class Solution {
public:
	int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> need;
		for (int i = 0; i < capital.size(); i++) {
			need.emplace(make_pair(capital[i],profits[i]));
		}
		priority_queue<int> can;
		while (k--) {
			while (need.size() && ( need.top().first <=w )) {
				can.emplace(need.top().second);
				need.pop();
			}
			if (can.empty()) { break; }
			w += can.top();
			can.pop();
		}
		return w;
	}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	int k, w;
	vector<int> profits,  capital;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			k = 2, w = 0, profits = { 1, 2, 3 }, capital = { 0, 1, 1 };
			auto res = Solution().findMaximizedCapital(k, w, profits, capital);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod01)
		{
			k = 3, w = 0, profits = { 1, 2, 3 }, capital = { 0, 1, 2 };
			auto res = Solution().findMaximizedCapital(k, w, profits, capital);
			AssertEx(6, res);
		}
		
	};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛