专题3 · 贪心（一）
贪心不是“瞎贪”，而是每一步都取当前最优、并相信它能堆出全局最优。
本讲带你建立「四步解题法」，并学会用反证 / 交换论证证明贪心真的对，最后用两道真题练手。
本讲你要带走的三件事
① 认得贪心
看到「选局部最优能拼出全局最优」的题面，能判断它大概率是贪心，并说出使用前提。
② 会写四步
用分解→定策略→求子最优→堆叠全局的固定流程落地代码，避免想到哪写到哪。
③ 敢证明
用反证 / 交换论证说明策略为什么不会更差，把「我觉得对」变成「能证明对」。
知识地图
本质
局部最优 → 全局最优
前提
无后效性、最优子结构
方法
排序 / 优先队列 / 选择
证明
反证法、交换论证
贪心：每一步都选「当前看起来最好」的
核心逻辑——选择每一阶段的局部最优，从而希望得到全局最优。前提是「局部最优一定会导致全局最优」。
🎯 经典例子：取十张钞票
桌上有十张钞票（100 / 50 / 20 / 10 / 5 / 1 元各若干），让你取一张使金额最大。
任何人都会选面值最大的那张——因为「取最大」这一步的局部最优，不会让之后的选择变差。这就是贪心。
⚠️ 什么时候贪心会翻车
- 选了当前最优，却堵死了后面更优的组合（有后效性）。
- 「局部最优」和「全局最优」目标不一致。
- 例：找零用最少张数——若面额是 1/3/4，付 6 元，贪心取 4+1+1（3 张）不如 3+3（2 张）。
🖼️ 看图：贪心为什么会翻车（付 6 元，面额 1 / 3 / 4）
贪心四步法（通用脚手架）
1分解子问题：把「全局最优」拆成一系列「每步选一个」的决定。
2确定贪心策略：这一步按什么规则选？常见是「按某个值排序后依次取」。
3求子问题最优解：实现「取当前最优」这一步（排序 / 优先队列）。
4堆叠全局最优：把每步结果累加 / 拼接，得到答案；注意数据类型与边界。
🧪 两种证明思路
- 数学归纳法：假设前 k 步最优，证第 k+1 步选局部最优后仍最优。
- 反证法 / 交换论证：假设存在一个更优解，把其中一步换成我们的贪心选择，证明不会变差（反而更好或等于），从而推翻「更优解」。
用「交换论证」说服自己
套路（背下来就能套）
第 1 步：写出贪心策略 G（比如「每次选差价最大的物品给小 B」）。
第 2 步：假设存在一个最优解 O 与 G 的第一次分歧发生在物品 i。
第 3 步：在 O 中把「给小 C 的物品 i」换成「给小 B（差价更大）」，总收入只增不减。
第 4 步：反复交换，O 被改成 G 且不更差 → G 也是最优解。得证。
常见题型与应对
🧩 基础贪心
- 区间问题：按结束时间排序（活动选择），或按开始时间排序。
- 分配问题：按对象属性排序后依次分配（本讲例题 2）。
- 排序问题：选最小 / 最大元素（本讲例题 1 优惠券）。
🔗 贪心 + 其他
- 贪心 + 枚举：先排序，再在有序结构上枚举。
- 贪心 + 动态规划：贪心定顺序，DP 在顺序上转移。
- 贪心 + 模拟：按贪心规则一步步执行（优惠券用券过程）。
ABC246C · 优惠券（AT_abc246_c）
📖 题意
有 N 件商品，第 i 件价 A_i 日元。你有 K 张优惠券，每张券可用于任一商品，同一商品可用任意张。对某商品用 k 张券，它的最终价变为 max{A_i − k·X, 0}。
求买下所有商品所需最小总金额。
约束：1 ≤ N ≤ 2×10⁵，1 ≤ K, X ≤ 10⁹，1 ≤ A_i ≤ 10⁹。
X 日元，直到它降到 0。5 4 7 | 8 3 10 5 13 → 答案 12（把 13→0、10→3、8→1，得 0+3+1+3+5=12）。优惠券 · 代码走读
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int main(){ ll n,k,x; cin>>n>>k>>x; vector<ll> a(n); ll sum=0; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } ll ret=0; for(int i=0;i<n;i++){ ret+=a[i]/x; a[i]%=x; } // ① 整 X 减 sort(a.begin(),a.end()); // ② 余数升序 if(k <= ret){ // ③ 券不够 ll s=0; for(int i=0;i<n;i++) s+=a[i]; cout << (ret-k)*x + s << "\n"; } else { // ④ 券够，再清最大余数 ll s=0; for(int i=0;i<n;i++) s+=a[i]; for(int i=n-1,u=k-ret; u>0 && i>=0; i--,u--) s-=a[i]; cout << s << "\n"; } return 0; }
🔍 四步对应
- 定策略：券永远给当前最贵商品。
- 求子最优：每件先整 X 减（省 X），余数归零。
- 堆叠全局：总省 = ret·X + 清掉的余数。
- 边界：K 可能极大，用整 X 批量减避免 O(K)。
优惠券 · 分步用券模拟器
GESP202503 五级 T1 · 平均分配（P11960）
📖 题意
小 A 有 2n 件物品。第 i 件，小 B 出价 b_i、小 C 出价 c_i。规定小 B、小 C 各恰好买走 n 件，求小 A 最大总收入。
约束：1 ≤ n ≤ 10⁵，0 ≤ b_i, c_i ≤ 10⁹。答案可能到 2×10¹⁴，必须用 long long。
n=3：b=[1,3,5,6,8,10] c=[2,4,6,7,9,11] → 答案 36。平均分配 · 代码走读
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; struct Item{ ll b,c,d; }; bool cmp(Item x,Item y){ return x.d > y.d; } // 差价降序 int main(){ int n; cin>>n; vector<Item> a(2*n); for(int i=0;i<2*n;i++) cin>>a[i].b; for(int i=0;i<2*n;i++) cin>>a[i].c; for(int i=0;i<2*n;i++) a[i].d=a[i].b-a[i].c; // ① 算差价 sort(a.begin(),a.end(),cmp); // ② 排序 ll ans=0; for(int i=0;i<n;i++) ans+=a[i].b; // ③ 前 n 件给 B for(int i=n;i<2*n;i++) ans+=a[i].c; // ④ 其余给 C cout << ans << "\n"; return 0; }
int 会溢出（2×10⁵ × 10⁹ ≈ 2×10¹⁴）。全用 long long，否则白丢 30 分钟。平均分配 · 差价排序分配模拟器
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
优惠券 · COUPON
第1档 · 2 分钟K == 0 或 X == 0 → 直接输出 sum(A)
第2档 · 8 分钟
每张券单独找「用了还能减最多」的那件商品，模拟 K 次
第3档 · 10 分钟
所有 A_i 相同 → 逐件用券直到用完或减到 0，可直接算
第4档 · 15 分钟
按 A_i 从大到小排序，每件用 min(剩余券, ceil(A_i/X)) 张
平均分配 · AVG
第1档 · 2 分钟n == 1 → 取 max(b₁+c₂, c₁+b₂)
第2档 · 8 分钟
枚举所有 C(2n, n) 种分配取最大，n ≤ 10 稳过
第3档 · 10 分钟
所有 c_i == 0 → 直接取 b 最大的 n 件给 B
第4档 · 15 分钟
按 (b_i − c_i) 从大到小排序，前 n 件给 B，其余给 C
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。易错辨析 & 当堂检测
💡 易错辨析
优惠券题若「每件直接减到 0 再处理下一件」，结果一定最优吗？
📝 当堂检测
平均分配题答案的数据类型应选？