502 IPO

哎呀，IPO 听着很唬人，其实咱只要盯住“当前能做里最赚钱的”就行啦。

题目描述#

咱来翻译下题面：现在有 n 个项目，每个项目都有两个信息：完成后能获得的纯利润 profits[i]，以及启动它之前必须拥有的最小资本 capital[i]。

一开始手里有资本 w，最多可以做 k 个不同项目。每做完一个项目，利润会立刻加到当前资本里，于是之后可能解锁更多原本做不了的项目。目标就是在最多做 k 个项目之后，让最终资本尽可能大。

思路#

这题看起来像是在一堆项目里挑挑拣拣，哎呀，直接暴力枚举项目顺序肯定不现实。关键观察是：每一轮只需要关心“当前资本 w 能启动哪些项目”，在这些可选项目里，选利润最大的那个就最划算。

为什么这个贪心是对的呢？因为项目利润会增加资本，而资本越大，只会让之后能启动的项目更多，不会让选择变差。所以在当前所有可启动项目中，如果不选利润最大的，而去选一个更小的利润，下一轮手里的资本只会更少，能解锁的项目也不会更多。那本姑娘当然要把当前能赚最多的先拿下啦。

实现上用两个堆配合。第一个是按启动资本排序的小根堆 cp_heap，里面放 (capital, profit)，方便不断找出当前最容易被解锁的项目。第二个是按利润排序的大根堆 p_heap，只放已经被当前资本解锁的项目利润。每一轮先把 capital <= w 的项目从 cp_heap 转进 p_heap，再从 p_heap 里取利润最大的项目执行，把利润加到 w 上。

如果某一轮转移完之后 p_heap 还是空的，说明当前资本一个项目都启动不了，继续循环也没有意义，直接结束。每个项目最多进出堆一次，整体时间复杂度是 O(n log n + k log n)，空间复杂度是 O(n)。

两个堆一配合，项目就像排好队一样，能做的先进来，最赚的先出发！

知识边界#

原题约束里的 profits[i] 是非负数，所以做一个项目不会让资本变少；如果项目可能亏钱，“最多做 k 个”就需要额外判断是否跳过负利润，不能直接套这份贪心。
本题的贪心选择依赖“利润加入资本后不会让未来选择变差”这个单调性；当前可做项目中选最大利润，可以让后续资本始终不劣。
两个堆分工不同：小根堆按 capital 管“什么时候能做”，大根堆按 profit 管“当前做哪个最赚”，这两个维度不能混在一个堆里硬凑。
gods 的 priorityqueue.NewWith 通过比较函数决定优先级：a[0] - b[0] 让资本小的先出，b - a 让利润大的先出。方向写反的话，答案会直接跑偏哦。

代码#

代码就按这套“双堆换乘”写下来，能启动的项目先上车，最赚钱的项目先出发——

import (
	"github.com/emirpasic/gods/v2/queues/priorityqueue"
)

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
	n := len(profits)
	// 小根堆：这里使用启动资本进行排序，放入 (capital,profits)对
	cp_heap := priorityqueue.NewWith(func(a, b [2]int) int {
		return a[0] - b[0]
	})
	// 大根堆：这里放入利润，同时使用利润从大到小
	p_heap := priorityqueue.NewWith(func(a, b int) int {
		return b - a
	})
	for i := 0; i < n; i++ {
		cp_heap.Enqueue([2]int{capital[i], profits[i]})
	}

	// 贪心策略：每轮先将当前资本 w 能启动的所有项目转入利润大根堆，
	// 再从中选取利润最大的项目执行，w 增大后下一轮再解锁更多项目
	for i := 0; i < k; i++ {
		for !cp_heap.Empty() {
			top, _ := cp_heap.Peek()
			if top[0] <= w {
				cp_heap.Dequeue()
				p_heap.Enqueue(top[1])
			} else {
				break
			}
		}
		if p_heap.Empty() {
			break
		}
		pro, _ := p_heap.Dequeue()
		w += pro
	}
	return w
}

好啦，这次的笔记就先到这啦。贪心不是每次都能放心用，但只要单调性站得住，堆就能把“当前最优”这件事安排得明明白白！