502.IPO
目录
1 问题描述
2 解题思路
贪心：要最大化最终资本，因此必然选择满足当前资本需要的纯利润最大的项目。
map<int, map<int, int>, std::greater<int>> projs
key为纯利润，value也是map，该map的key为启动所需最小资本、value为项目数量。
3 代码
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
map<int, map<int, int>, std::greater<int>> projs;
for (int i = 0; i < profits.size(); i++) {
projs[profits[i]][capital[i]]++;
}
for (int i = 0; i < k; i++) {
int find_flag = 0;
for (auto &prj : projs) {
if (w >= ((prj.second).begin())->first) {
w += prj.first;
prj.second.begin()->second--; // 该项目已经完成
if (prj.second.begin()->second == 0)
prj.second.erase(prj.second.begin());
if (prj.second.empty())
projs.erase(prj.first);
find_flag = 1;
break;
}
}
if (find_flag == 0) // 如果任何项目的最小资本需求都不能满足，就要结束IPO
return w;
}
return w;
}
};