假设 力扣（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。
来源：力扣（LeetCode）
读题
- 最多做 k 个不同项目
- 做项目不花钱，只看自己的钱够不够成本。w >= capital[i]
要求：最大化的最终持有资本。
读完题，就一个感觉，要干就干最能挣钱的，这不是让我贪心吗？好家伙，冲冲冲...
解题思路
讲个故事先
你是 LeetCode CEO，将要走向巅峰 IPO，为了想拉高股票价格多（割）赚（韭）钱（cai），你要在限定项目次数内尽可能的多挣钱。
你的初始资本为 w，做项目空手套白狼不花钱。需要注意的是你的资本 w 需要 >= 想干项目所需的成本，这项目只能干一次。
- 首先，你只能干 k 个项目。那肯定得每次干的项目都得最赚钱，这样你的资本 w 就增长，持有资本越多就能干更大更赚钱的项目。
- 好，咱来干第一票，得选所有能干的项目中最赚钱的，咋办？ 先把项目按照所需资本从小到大 sort 一下。然后做最赚钱的那个项目。咱做了最赚钱的项目，空手套白狼，不花钱。同时呢，咱初始资产 + 这第一票赚的钱，持有资本增长了，那不得赶紧物色下一个最赚钱的。
- 之后操作就像这第一票一样，直到干完 k 次。
- done，你本次临时当 CEO 所持有的的最终最大资本就出来了。
回到代码层面
- 上边小故事里说了要把项目所需资金从小到大排序一下。
- 用一个优先队列
priority_queue<int> q，每次循环时候将项目所需资金小于所持资本 w 的项目利润放入优先队列 q，自动排序。每次取 q 的 top()，更新 w。然后如是这般循环 k 次即可。
贪心其实就是像这样每一个小阶段局部最优，然后就可以推到全局最优。就像这题每次干最赚钱的，最后就能得到最大持有资本。
PS:
-
Q: C++ sort 对
vector<pair<int, int>>优先比较 pair.first，然后比较 pair.second ? -
A:
std::sort可以不写比较函数，不写排序函数的话就用operator<来比较。而std::pair::operator<按标准，两个 std::pair 的 first 为第一优先级，second 为第二优先级。
template <class _Ty1, class _Ty2>
_NODISCARD constexpr bool operator<(const pair<_Ty1, _Ty2>& _Left, const pair<_Ty1, _Ty2>& _Right) {
return _Left.first < _Right.first || (!(_Right.first < _Left.first) && _Left.second < _Right.second);
}
代码
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
vector<pair<int, int>> info;
int size = profits.size();
for(int i = 0; i < size; i++) {
info.push_back({capital[i], profits[i]});
}
sort(info.begin(), info.end());
priority_queue<int> q;
int idx = 0, iSize = info.size();
while(k--){
while(idx < iSize && w >= info[idx].first) {
q.push(info[idx++].second);
}
if(q.empty()) {
break;
}else {
w += q.top();
q.pop();
}
}
return w;
}
};
补充&鸣谢
在此非常感谢代码随想录。这位老哥的 leetcode 刷题笔记分类整理不同算法类型，也有不同语言版本，对于菜鸡的我来说帮助很大。
另外，我也整了个刷题笔记，坚持费曼学习法，吃进去，产出来。
如果感觉本题解对你有帮助，请不要吝啬点赞👍🏻啊 冲冲冲...
网友评论