ZYF059 最大开支
ZYF059 最大开支
【算法】 贪心、优先队列
【C++】 priority_queue、long long、结构体、函数
【难度】 普及−
一、题目简述
有 个人和 个娱乐项目。第 个项目的门票单价与团购人数 的关系为:
当团购人数足够多使得 时,该项目的门票免费()。
每个人最多选一个项目(也可以不选)。如果 人选了项目 ,该项目总收入为 。
小蓝想知道:至少需要准备多少钱,才能保证无论大家怎么选都付得起? 换句话说,就是求所有人选择方案中,总花费的最大值。
| 变量 | 范围 |
|---|---|
| (人数) | |
| (项目数) | |
关键点: 一定为负数,意味着团购人数越多,单价越低(甚至免费但总收入可能下降)。
二、解题思路
2.1 问题转化
定义项目 在 人时的总收入函数:
当 时,,这是一个开口向下的二次函数(因为 ),具有边际收益递减的特点。
我们的目标:在 的约束下,最大化 。
2.2 为什么贪心是对的?
考虑"多派一个人去项目 "的边际收益(即总收入的增量):
当 且 时,可以算出:
因为 ,所以 随 增大而严格递减。也就是说,每多派一个人,收益的增加量越来越小,最终变为负数或零。
这恰好是贪心算法的经典条件:每个项目的"边际收益序列"是递减的,我们只需要每次挑"当前边际收益最大"的项目加人,直到边际收益 或人数用完。
2.3 手动模拟
以样例为例:,,,。
项目 1 的边际收益序列(从 开始):
| 加第几人 | ||||
|---|---|---|---|---|
| 第 1 人 | 1 | 6 | ||
| 第 2 人 | 2 | ❌ |
项目 2 的边际收益序列:
| 加第几人 | ||||
|---|---|---|---|---|
| 第 1 人 | 1 | 5 | ||
| 第 2 人 | 2 | 1 | ||
| 第 3 人 | 3 | ❌ |
将所有 的值从大到小排列:6(项目 1)、5(项目 2)、1(项目 2)。取前 个(实际只有 3 个大于 0),总和为 。
这就是最大总花费,对应方案:1 人去项目 1(花费 6),2 人去项目 2(花费 6)。
2.4 算法步骤
- 对每个项目 ,计算 ,若 则入堆
- 重复以下步骤,直到堆空或已分配 人:
- 弹出堆顶(当前最大边际收益)
- 若 ,结束
- 累加 到答案
- 计算该项目再加一人的边际收益,若 则重新入堆
- 输出答案
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 5;
long long k[M], b[M];
int main() {
int n, m;
cin >> n >> m;
// 大根堆:存 (边际收益, 项目编号, 该项目已分配人数)
priority_queue<tuple<long long, int, int>> pq;
for (int i = 1; i <= m; i++) {
cin >> k[i] >> b[i];
// f_i(1) = max(K_i + B_i, 0)
long long gain = max(k[i] + b[i], 0LL);
if (gain > 0) {
pq.push({gain, i, 1});
}
}
long long ans = 0;
int used = 0; // 已分配的人数
while (!pq.empty() && used < n) {
auto [delta, id, x] = pq.top();
pq.pop();
if (delta <= 0) break; // 边际收益非正,停止
ans += delta;
used++;
// 计算该项目再加一人的边际收益
int nx = x + 1;
// f(x) 和 f(x+1),注意 H(X) = max(KX + B, 0) 可能为 0
long long curH = k[id] * x + b[id];
long long nxtH = k[id] * nx + b[id];
long long curF = (curH > 0) ? x * curH : 0;
long long nxtF = (nxtH > 0) ? nx * nxtH : 0;
long long nextDelta = nxtF - curF;
if (nextDelta > 0) {
pq.push({nextDelta, id, nx});
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是所有项目边际收益为正的人数之和。每次堆操作 ,最多执行 次。由于 ,在时限内绰绰有余。
- 空间复杂度:,堆中最多同时存 个元素。
五、知识扩展
5.1 为什么不用 DP?
看到"分配 个人到 个项目"容易想到背包 DP。但 , 的 DP 显然不行。本题利用 带来的边际收益递减性质,用贪心得到了最优解。
5.2 贪心正确性的更严谨理解
每个项目 的边际收益序列 是单调不增的。问题等价于:从 条递减序列中选出不超过 个元素,使总和最大——这自然就是"每次选当前最大"的策略,和"把所有人混在一起排序取前 个"等价。
5.3 易错点
- 可能为 0:当 时门票免费,总收入为 0。此时边际收益为负数,不应继续加人。代码中用
max(K_i + B_i, 0LL)和判断curH > 0来处理。 - 使用
long long: 可达 , 可达 ,int会溢出。 - 入堆条件:只有 才入堆, 加不加人都一样,入堆只会浪费时间。
- 边际收益递减的证明:当 且 时,,斜率 ,严格递减。✅
5.4 类似题目
- 本题本质上是一个可分离凸(凹)资源分配问题,在各类 OJ 中以不同面貌出现
- 洛谷 P4053 建筑抢修 —— 类似的贪心+堆思路
- LeetCode 253. 会议室 II —— 堆维护当前最优选择
