ZYF058 IPO
ZYF058 IPO
【算法标签】 贪心
【语法标签】 :结构体(struct)、sort、自定义比较函数(cmp)、优先队列(priority_queue)、cin/cout、for循环、while循环、数组
一、题目概述
假设你手上有 个项目可以投资(),每个项目 有两个属性:
- :完成项目后能获得的纯利润()
- :启动该项目至少需要的资本()
你初始拥有资本 (),最多只能完成 个不同的项目()。
每完成一个项目,获得的利润会立刻加到总资本中,使你能够启动更多项目。
求:完成最多 个项目后,能达到的最大资本。
输入格式:
- 第一行:三个整数
- 第二行: 个整数
- 第三行: 个整数
输出格式:
- 一个整数,表示最终的最大资本
样例:
输入:
3 2 0
1 2 3
0 1 1
输出:
4解释:
- 初始资本 ,能做项目 0(需求资本 0),获得利润 1,资本变为 1
- 资本 1 时,能做项目 1(需求 1,利润 2)和项目 2(需求 1,利润 3),选利润最大的项目 2
- 资本变为 ,已经完成 个项目,停止
- 最终资本 = 4
二、解题思路
数据规模分析
- ,:需要 或 的算法。
- 和 可达 :使用
int足够(),也可以用long long更安全。 - , 个项目利润累加最多 量级,
int可以存下。
核心策略:贪心
要让最终资本最大,直觉上每一步都应该选:当前资本够启动的、利润最大的项目。
但是如果每步都扫描所有项目去找最大利润,复杂度 会超时。我们需要一个高效的方式,在"能做"的项目中快速找到利润最大的那个。
数据结构设计
双数据结构配合是本題的关键:
数组 + 排序:把所有项目按所需资本从小到大排序。这样我们用一个指针
idx从前往后扫描,"资本 当前资金"的项目是连续的一段,可以一次性全部"解锁"。大根堆(优先队列):存放已经被解锁的项目的利润。堆顶永远是最大利润,取数 ,插入 。
默认的 priority_queue<int> 就是大根堆,无需额外参数。
手动模拟样例
以 n=3, k=2, w=0, profits=[1,2,3], capitals=[0,1,1] 为例:
预处理: 按 capital 升序排列项目。
| 项目编号 | 利润 profit | 需求资本 capital |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2 | 1 |
| 2 | 3 | 1 |
逐步模拟:
| 轮次 | 当前资本 w | 指针 idx | 解锁的项目 | 大根堆内容 | 选择 | w 更新 |
|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | — | [] | — | 0 |
| 第 1 轮 | 0 | 0→1 | 项目 0(capital=0≤0) | [1] | 堆顶=1(项目0) | 0+1=1 |
| 第 2 轮 | 1 | 1→3 | 项目 1(capital=1≤1) | [2, 3] | 堆顶=3(项目2) | 1+3=4 |
| 项目 2(capital=1≤1) | ||||||
| 结束 | 4 | — | k=2 轮已完成 | — | — | 4 |
注意:第 2 轮资本变为 1 后,idx 指针从 1 扫描到 3,把项目 1 和项目 2 都解锁了。堆中同时有 2 和 3,我们取最大的 3。
算法流程
- 将 个项目打包成结构体数组,按
capital升序排序。 - 维护一个大根堆
pq和一个数组指针idx = 0。 - 循环 次(最多做 个项目):
- 解锁阶段:只要
idx < n且a[idx].capital <= w,就把a[idx].profit加入大根堆,idx++。 - 选项目阶段:如果堆不为空,弹出堆顶(最大利润),加到 中。如果堆为空,说明没有项目可做,提前退出。
- 解锁阶段:只要
- 输出最终的 。
为什么这样做是对的?
贪心的最优性可以从两方面理解:
每步局部最优 → 全局最优:因为我们每一步都选了当前能做的项目中利润最大的,这意味着我们用"单位资本"换来了最大的资本增长。更大的资本能解锁更多项目,形成正向循环。
排序保证了"解锁"的完整性:按 capital 排序后,先前被解锁但没来得及选的项目,利润仍然留在堆中。随着资本增长,它们的 capital 条件仍然满足,所以不会漏掉。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
// 项目结构体:p = 利润,c = 所需资本
struct Project {
int p, c;
};
Project a[N];
// 按所需资本从小到大排序
bool cmp(Project x, Project y) {
return x.c < y.c;
}
int main() {
int n, k, w;
cin >> n >> k >> w;
// 读入利润
for (int i = 0; i < n; i++) {
cin >> a[i].p;
}
// 读入所需资本
for (int i = 0; i < n; i++) {
cin >> a[i].c;
}
// 按所需资本升序排序
sort(a, a + n, cmp);
// 大根堆:存放已解锁项目的利润,堆顶最大
priority_queue<int> pq;
int idx = 0; // 指向下一个待解锁的项目
// 最多做 k 个项目
while (k--) {
// 解锁阶段:把所有资本 ≤ 当前资金的项目利润加入堆
while (idx < n && a[idx].c <= w) {
pq.push(a[idx].p);
idx++;
}
// 如果没有可做的项目,提前退出
if (pq.empty()) {
break;
}
// 选择利润最大的项目
w += pq.top();
pq.pop();
}
cout << w << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,简化为 。
- 排序:
- 每个项目最多入堆一次、出堆一次,堆操作每次 。总堆操作次数 (入堆)(出堆)。
- 空间复杂度:。
- 结构体数组
a[N]占 - 优先队列最多存放 个元素的利润
- 结构体数组
五、易错点
k可能大于n:循环 次没问题,因为当所有项目都入堆并被选完后,堆会变空,代码中的if (pq.empty()) break;会正确处理提前退出。排序的稳定性:capital 相同的项目排序后相对顺序不重要,因为我们把所有满足条件的项目利润都加入了大根堆,堆会帮我们选出最大的。
指针不要回退:
idx只会增加不会减少,因为资本 只会增加(利润非负),之前解锁过的项目不会因为条件不满足而被"锁回去"。大根堆 vs 小根堆:本题需要每次取最大利润,所以用默认的大根堆。注意区分前面两道"合并"问题用的是小根堆。
区分技巧:每次选"最小的"用小根堆(合并果子),每次选"最大的"用大根堆(IPO)。关键看贪心方向:是优先处理小的,还是优先处理大的。
