0502. IPO¶
题目信息¶
- 题号:
0502
- 难度:
Hard
- 主题:
项目选择、资本门槛、利润累积、最多执行次数
- 原题:
- 重点:
每个项目最多选择一次、只有资本达到门槛时才能启动、利润立即加入资本、最多选择 k 个项目
题目重述¶
有 n 个项目,第 i 个项目需要至少 capital[i] 的当前资本才能启动,完成后会获得 profits[i] 的净利润。初始资本为 w,最多可以选择并完成 k 个不同项目。
每完成一个项目,其利润立即加入当前资本,因此可能解锁新的项目。返回经过至多 k 次选择后能够得到的最大资本。profits 和 capital 长度相同,每个项目只能使用一次;允许少于 k 次选择。
自建示例¶
资本逐步解锁项目:
输入:k = 2,w = 0,profits = [2,5,1],capital = [0,3,1]
输出:3
解释:先完成资本门槛为 0、利润为 2 的项目,资本变为 2;随后可完成利润为 1 的项目,最终资本为 3。利润为 5 的项目仍需资本 3,且两次选择已经用完。
初始资本足以直接选择最佳项目:
输入:k = 1,w = 4,profits = [3,6],capital = [0,4]
输出:10
解释:两个项目都可启动,只能选择一个,因此选择利润为 6 的项目。
资本可达项目中的利润最大化¶
把项目按资本门槛从小到大排序,并用指针把当前资本已经能够启动的项目全部加入最大堆。每次选择时,从堆顶取利润最大的项目;它不会减少资本,且在当前可选集合中给出最大的下一步资本,因此选择后再继续扩展可达项目。
若最大堆为空,说明剩余项目的门槛都超过当前资本,无法继续选择,直接结束而不强行凑满 k 次。
C++ 实现¶
class Solution {
public:
int findMaximizedCapital(int k, int w,
std::vector<int>& profits,
std::vector<int>& capital) {
std::vector<std::pair<int, int>> projects;
for (int i = 0; i < static_cast<int>(profits.size()); ++i) {
projects.push_back({capital[i], profits[i]});
}
std::sort(projects.begin(), projects.end());
std::priority_queue<int> available;
long long current = w;
int next = 0;
for (int step = 0; step < k; ++step) {
while (next < static_cast<int>(projects.size()) &&
projects[next].first <= current) {
available.push(projects[next].second);
++next;
}
if (available.empty()) break;
current += available.top();
available.pop();
}
return static_cast<int>(current);
}
};
代码分析¶
每一步真正影响后续选择的不是已经做过哪些项目的完整顺序,而是“当前资本下哪些项目已经可做”以及完成后能增加多少资本。把所有项目按 capital 从小到大排序后,随着当前资本增加,只需用一个指针把新达到门槛的项目加入候选集合;已经加入的项目都满足当前门槛,未加入的项目都还不能启动。
候选集合中应选择利润最大的项目。设当前资本为 w,候选项目的利润为 p,另一个可选项目的利润为 q 且 p >= q。先做 p 后资本至少和先做 q 一样多;若某个后续方案原本还会做 p,可以把它与第一步交换,因为 p 当前已经可做,而原第一步的项目在资本变多后仍然可做。交换后完成相同数量的项目,资本不会更低,后续项目也不会因此失去可行性。若后续方案根本没有使用 p,直接用 p 替换第一步同样不会降低结果。因此每一步取当前最大利润不会排除更优解。
例如 k=2、初始资本为 0,项目为 (capital, profit) = (0,2),(3,5),(1,1)。第一次只有利润 2 的项目进入堆,完成后资本为 2;指针继续把门槛 1 的项目加入堆,此时堆顶是利润 1,第二次选择后资本为 3。门槛 3、利润 5 的项目虽然随后已经可做,但选择次数已经用完。这个过程也说明了“选择后重新扩展候选集”是必需的,不能在一开始只看初始资本。
排序数组的指针保证每个项目只入堆一次,最大堆保证每次弹出的都是当前可行项目中的最高利润,弹出本身也保证项目不会重复选择。若堆为空,说明所有剩余项目的资本门槛都高于当前资本;由于项目利润不会凭空增加资本,继续等待或强行选择都不可能合法,所以应提前结束。题目只要求最多选择 k 个项目,少于 k 个是合法结果。
正确性由贪心交换和候选集合不变量共同保证:指针循环结束后,堆中恰好是尚未选择且资本门槛不超过当前资本的项目;堆顶选择在当前步可行且对下一步资本最有利;交换论证说明任何最优方案都可以把该选择放到当前步而不变差。重复 k 次或候选耗尽后,得到的资本即为可达到的最大值。
projects 保存门槛和利润的对应关系,next 只向前移动;每轮先完成入堆,再弹出一个最大利润,正好对应“利润立即回到资本并解锁新项目”的题意。排序、每次入堆和出堆合计时间复杂度为 O(n log n + k log n),额外空间复杂度为 O(n);current 使用 64 位整数保存中间资本,最后按题目接口返回整数。