IPO

两件事配合:① 把项目按门槛 capital 升序排好,本金涨了就把新够得着的「解锁」进候选池;② 候选池用大根堆装利润,随时一秒取出最大的那个,不用每轮重新扫。

盯住下面三样怎么变:指针 ptr(沿排好序的项目往右推,负责解锁)、大根堆(装解锁项目的利润,堆顶永远最大)、本金 w(每取一个堆顶就涨一次)。

第 0 步 · 按 capital 升序排好：项目按门槛 capital 从小到大排好(本例 capital=[0,1,2,3,4] 已升序)。指针 ptr 从最左开始,只往右走,把本金够得着的项目利润送进大根堆。本金 0,还能做 3 个。

第 1 轮 · 解锁:本金 0 够得着谁?：指针停在项目 0:门槛 0,本金 0 够得着,把它利润 2 送进堆。再看项目 1,门槛是 1,本金不够,指针就先停在这,等本金涨了再往右。

项目0 入堆 · 利润 2：候选池(大根堆)里现在只有一个利润 2。堆顶永远是当前能做的项目里利润最大的——现在就它一个。

第 1 轮 · 取堆顶:做利润 2 的项目：从堆顶取出利润 2 做掉,本金从 0 涨到 2。堆空了。关键:本金一变大,原本够不着的项目可能解锁了——下一轮先回去推指针补充候选。

第 2 轮 · 解锁:本金涨到 2：本金涨到 2,指针往右推。项目 1 门槛 1,够得着,利润 5 入堆。项目 0 已用过(灰)。本金 2 还够不够下一个?继续看。

项目1 入堆 · 利润 5：利润 5 进堆,成为新堆顶。但解锁阶段还没结束——本金 2 也够得着门槛为 2 的项目 2,接着把它也解锁进来,再决定取谁。

第 2 轮 · 继续解锁:门槛 2 也够：本金 2 也够得着门槛 2 的项目 2,利润 8 一起入堆。再看项目 3,门槛 3,本金不够,指针停下。这一轮一口气解锁了两个项目,候选池里有两个了。

项目2 入堆①·先挂到堆底：入堆分两步。第一步:新利润 8 先塞到堆的最末尾(成为 5 的孩子)。这时堆顶暂时还是 5,但 8 比父亲大,违反了大根堆的规矩,接下来要让它往上「冒泡」。

项目2 入堆②·上浮:8 比父亲 5 大：第二步「上浮」:新来的 8 和父亲 5 比,8 更大就交换,一路往上冒,直到比父亲小或到顶。这里 8 一步就冒到了堆顶,5 沉下去当它的孩子。这就是堆维持「堆顶最大」的内部动作。

第 2 轮 · 取堆顶:做利润 8 的项目：取出堆顶 8 做掉,本金 2 → 10!利润 5 没被取走,继续留在堆里当候选。本金涨到 10,后面门槛更高的项目这下也够得着了。

第 3 轮 · 解锁:本金 10 一次解锁剩下全部：本金 10 远超剩下项目的门槛。指针先推到项目 3(门槛 3),利润 3 入堆。还有项目 4 没看,接着推。

项目3 入堆 · 利润 3：利润 3 进堆,但它比堆顶 5 小,沉到 5 下面当孩子,5 仍是堆顶。本金 10 还够得着最后的项目 4,继续解锁。

第 3 轮 · 继续解锁:最后一个项目4：项目 4 门槛 4,本金 10 够得着,利润 6 入堆。指针走到末尾,所有项目都解锁完了,以后不再回头。

项目4 入堆①·先挂到堆底：和刚才一样:新利润 6 先挂到堆的最末尾。它的父亲是堆顶的 5。6 比父亲 5 还大,又违规了,所以下一帧要让 6 往上冒。

项目4 入堆②·上浮:6 比父亲 5 大：6 和父亲 5 交换,6 上浮成新堆顶,5 沉下去当孩子,3 没动。现在候选池里有 6、5、3 三个,堆顶是 6。最后一个名额该花在它身上。

取堆顶①·末尾补位 + 下沉：取堆顶不是简单删掉:先把堆顶 6 拿走,再把末尾的 5 搬到堆顶补空,然后让它和孩子比、必要时一路「下沉」。这里 5 比孩子 3 大,停在顶上,堆依然合法。

第 3 轮 · 做利润 6 的项目完成：取出堆顶 6,本金 10 → 16。这是第 3 个项目,k 用完了,循环结束。堆里还剩利润 5、3 的项目虽做得起,但名额没了——这正是贪心:把有限的 k 个名额砸在最值钱的项目上。

整轮回放 · 做了项目 0 / 2 / 4：整道题就这个循环:本金涨了就推指针解锁新项目入堆,再从堆顶取利润最大的做掉。绿勾标出真做的三个(利润 2、8、6),本金一路涨到 16,和手算一致。

别贪「门槛最低」或「最先解锁」的——解锁只决定能不能做,真正决定收益的是利润。一旦解锁,就该在所有候选里挑利润最大的,这才让本金涨最快、解锁更多项目。

提速对比：核心提速:用大根堆替代每轮重扫。每个项目一生只进堆一次、出堆一次,取最大利润只要 O(log n),不再做重复劳动。

易错实演 · 堆空了必须 break：如果某一轮一个项目都解锁不了,堆就是空的。这时必须 break 提前结束,不能硬去取堆顶,否则会对空堆操作报错。

边界三连：边界都围绕「做不满 k 个」和「一开始就做不起」:靠堆空 break 兜底,本金不够时原样返回。

面试追问：面试官常追问 Python 大根堆的实现、利润为负的边界、以及双堆替代排序的写法。