刷题的时候看到AT_abc441_c题目名就叫Sake or Water清酒还是水我第一反应是这题跟喝酒较上劲了。等把题面看完才明白出题人其实是借“清酒还是水”这个日常二选一考一个非常经典的贪心套路先定基准、再算增量、排序取前K。这篇文章就把这道C题的完整思路捋一遍从读题到证明再到 AC 代码顺便聊聊从这道题抽象出来的“差值贪心”模型能用到哪些场景。无论你是刚开始刷贪心的新人还是已经被“选K个最优”绕晕的老选手这篇都能给你一套可复用的思路框架。1. 先把题意说清楚Sake or Water 到底让我们做什么1.1 这道 C 题长什么样先把题意用大白话压缩成一句话有 N 个宴会场次每个场次提供一杯清酒和一杯水你必须在每场二选一喝掉其中一杯。喝清酒会获得美味值s_i喝水会获得清爽值w_i。但肚子有限全场下来喝清酒的总杯数不能超过 K。问怎么安排每一场的选择才能让总得分最大。这类题目在 ABC 系列的 C 题位置很常见一般不会把数据范围写得特别吓人但绝不会让你用暴力枚举拿到分。按常规规模来估计N 大概在 2×10⁵ 级别s_i和w_i的绝对值可能到 10⁹总和的规模会到 10¹⁴ 以上这一点后面写代码时非常关键。先看一个微型样例找感觉场次清酒美味值 s水清爽值 w差值 d s - w11046238-53725如果限制 K 1也就是全场最多只能喝一杯清酒。最简单粗暴的想法是把“选哪一杯清酒”的三种情况都列出来全喝水4 8 2 14只把第1场换成清酒10 8 2 20只把第2场换成清酒3 4 2 9只把第3场换成清酒7 4 8 19最优是 20对应“把第 1 场换成清酒”。观察这个结果第 1 场的差值 d 6 是三场里最大的换成清酒带来的净收益最高。这不是巧合而是这道题真正的解题入口。1.2 我看到这题的第一反应见到“二选一 数量上限”的结构我脑子里会自动弹出一个画面食堂套餐默认配米饭你可以额外花钱把其中某些份的米饭换成面条但升级次数有限每次换的“差价”不一样。想吃到最爽的组合当然优先换差价最大的那些对吧“Sake or Water”这道题就是这么回事。每个场次都有一个“默认选项”和一个“备选选项”默认选项不消耗受限的资源水随便喝备选选项消耗一个稀有额度清酒杯数 K。你真正需要决策的不是“每一场怎么选”而是“把哪些场次从默认切到备选能让总分涨得最多”。很多人在这一步会卡住是因为他们试图同时决定 N 场的每一个选择组合数爆炸自然想不出头绪。正确的做法是先固定一个轻松成立的方案再考虑在这个方案上做替换。这个“先定基线、再算增量”的思维转换是解这一类题的第一课。2. 差值贪心为什么能成立把“选清酒”看成“替换掉水”2.1 全选水的基准线核心等价变形我先把“选清酒”这件事彻底改写成数学形式。假设我们先把所有场次都暂时定为喝水此时得到一个基准总分base w₁ w₂ ... w_N这个方案显然满足“清酒杯数不超过 K”的限制因为清酒杯数是 0。接下来如果我把第 i 场从喝水改成喝清酒总分会发生什么变化原本贡献是w_i改成清酒后贡献是s_i净变化就是d_i s_i - w_i也就是说任意一个最终的合法方案它的总分都可以写成总分 base (所有被换成清酒的场次的 d_i 之和)这一步非常关键因为它把“每个场次二选一”的复杂决策完完全全转化成了“从一堆数字d_1, d_2, ..., d_N里挑一些加到 base 上去”而约束是“最多挑 K 个”。为什么这个转换有效因为每个场次之间是独立的喝第 1 场的清酒不会影响第 2 场清酒带来的 d₂每个 d_i 都是固定常量。问题就这样从“排列组合式的方案枚举”降维成“批量挑数相加”的单纯问题。2.2 交换论证为什么最优解必然是“取最大”很多教材讲贪心时喜欢直接说“排个序取最大的 K 个”但作为刷题的人我必须知道这句话背后的逻辑否则换个外壳就不敢认了。这里可以用一个教科书级的论证——交换论证。假设有一个方案 S它不是“取 d 最大的 K 个”。那么在这个方案里一定存在两种情况方案选的杯数低于 K但存在某个尚未选中的场次 j 满足 d_j 0。方案选了某个场次 i却漏掉了某个场次 j且 d_j d_i。对于情况 1把 j 加进清酒选择里总分立刻增加 d_j方案变得更优因此原来不是最优。 对于情况 2把 i 从清酒选择里拿掉、换成 j清酒杯数不变总分的变化是d_j - d_i 0方案也变优了。反复进行这样的替换任何不是“选了最大那批 d”的方案都能被改进。因此最优解一定落在“优先选择 d 最大的那些场次换成清酒”上面。这里有个细节必须强调上面论证实际上依赖一个前提那就是“清酒杯数不能超过 K”。题面如果写的是“最多 K 杯”那负的 d 会拖累总分我们不应该选题面如果写的是“恰好 K 杯”那就算 d 全是负的也必须硬着头皮补足 K 杯只能选“负得最少”的那 K 个也就是前 K 大的 d哪怕它们小于 0。2.3 “最多 K”和“恰好 K”的语义陷阱一字之差代码完全不同竞赛最怕的不是思路不会而是题目读漏一个词。同一个故事限制措辞不同解法分支就不同我把两种版本的核心结论放在一起限制说法选择策略代码行为清酒杯数最多 K≤ K所有正的 d 都值得选但最多选 K 个排序后取前 K 个遇到 d ≤ 0 立即停止清酒杯数恰好 K K必须选满 K 个哪怕 d 是负数排序后无条件取前 K 个清酒杯数至少 K≥ K先选所有正 d不够 K 个再补负 d排序后先取所有正再按需补负拿前面那个样例来说d [6, -5, 5]K 1“最多 1 杯”选正的且最大的那个d 6答案 base 6 20。“恰好 1 杯”前 1 大的就是 6答案也是 20看起来一样。但如果 K 2“最多 2 杯”还是选 6 和 5答案 25“恰好 2 杯”只能选 6 和 -5答案 9。差异一下就出来了。我建议读题的时候把“最多 / 恰好 / 至少”这三个词圈出来写完代码后对着这个关键词再检查一遍逻辑分支。这一条对任何“选 K 个”型题目都适用。3. 落地代码与当场翻车点排序、累加、边界处理3.1 可 AC 的 C 与 Python 写法思路已经闭环代码其实非常短。C 版本我建议这么写#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; long long K; cin N K; long long base 0; vectorlong long d(N); for (int i 0; i N; i) { long long s, w; cin s w; base w; // 先把所有场次都当作喝水累加基准 d[i] s - w; // 计算把这一场换成清酒的增量 } sort(d.rbegin(), d.rend()); // 从大到小排序 for (int i 0; i K i N; i) { if (d[i] 0) break; // “最多K杯”语义负增量不选 base d[i]; } cout base \n; return 0; }Python 版本逻辑完全一致import sys def main(): input sys.stdin.readline N, K map(int, input().split()) base 0 diffs [] for _ in range(N): s, w map(int, input().split()) base w diffs.append(s - w) diffs.sort(reverseTrue) for d in diffs: if K 0: break if d 0: break base d K - 1 print(base) if __name__ __main__: main()为什么用sort(d.rbegin(), d.rend())而不是先升序再反转因为rbegin()直接返回反向迭代器排序后容器里就是从大到小排列代码意图更直观也少写一行reverse。这种小习惯看起来无所谓但在比赛里能帮你减少一步操作也就少一步出错的可能。复杂度是 O(N log N)主要在排序上。N 在 2×10⁵ 时这个复杂度在大多数评测环境下都能稳稳跑进 1 秒不需要额外优化。3.2 三个最容易写错的细节第一读入顺序颠倒。这类题目输入通常是“每行两个数”但顺序到底是s w还是w s不同题不一样。我见过太多选手因为把美味值和清爽值读反样例怎么也推不出来最后发现只是读入顺序问题。建议先用样例手算一遍确认第一个数对应什么含义。第二整数溢出。这是这道题埋得最深的一颗雷。s_i和w_i的绝对值如果到 10⁹N 是 2×10⁵那么 base 和 d 的累加量级轻松突破 2×10¹⁴早就把 32 位 int 撑爆了。C 里所有数值变量都要用long longPython 不需要担心单个数溢出但也要注意逻辑上别把 N 和 K 弄反类型。第三K 和 d[i] ≤ 0 的 break 位置。很多人会写成for (int i 0; i K; i)然后循环里忘记判断i N。如果题面里 K 可能大于 N虽然通常不会但有备无患这一步就会越界访问。更隐蔽的问题是 break 的判断条件在“最多 K 杯”语义下一旦当前 d[i] ≤ 0后面的 d 只会更小全部没有必要选直接 break 是安全的但如果你把这道题误读成“恰好 K 杯”这个 break 就会让你丢掉必须补满的负数导致答案偏大。3.3 用对拍和极端样例验证自己没写错实战中我推荐一个“暴力对拍”的思路。数据规模小的时候写出一个枚举所有方案的暴力函数再和贪心解法对比// 暴力版本仅用于 N 很小的数据验证 long long brute(vectorint s, vectorint w, int N, int K) { long long best 0; for (int mask 0; mask (1 N); mask) { int cnt 0; long long val 0; for (int i 0; i N; i) { if (mask i 1) { cnt; val s[i]; } else { val w[i]; } } if (cnt K) best max(best, val); } return best; }然后在本地随机生成 N ≤ 15 的小数据把暴力结果和贪心结果反复比对。一旦跑一次发现不同就说明要么源代码有 bug要么你对题面语义的理解有偏差。这个方法比肉眼盯代码高效得多我强烈建议刷题时养成对拍的习惯。另外造极端样例也有讲究全取正差、全取负差、差值全为 0、K 0、K N这几类边界情况一定要人工验一遍。K 0 时答案应该是全喝水K N 且所有 d 为正时答案应该是全清酒K N 但存在负 d 时“最多 K”的正确答案依然是全喝水因为负增量全部跳过。4. 脱掉清酒外衣一类差值贪心题的通解4.1 骨架模型很少的代码很宽的适用范围做完这道题之后我把它抽象成了一个骨架模型有 m 个独立元素每个元素提供两种状态 A 和 B两种状态各自产生一个数值。选择某种状态有数量限制目标是最优化总数值之和。这个模型的通解只有三步计算所有人都在 B 状态下的基准值base sum(B_i)。计算每个人从 B 切到 A 的增量delta_i A_i - B_i。对 delta 从大到小排序在限制数量内累加合适的增量到 base。写成伪代码模板就是base 0 deltas [] for 每个元素 i: base B_i deltas.append(A_i - B_i) sort(deltas, reverseTrue) for delta in deltas: if 超过限制: break if delta 需要被拒绝: break # 最多语义时 delta 0 base delta print(base)模板一共不到十行但能覆盖的题目却非常多。关键就在于你有没有识别出“两种状态 数量限制 独立贡献”这三个特征。4.2 三个经典同构变体变体一选课学分问题。每学期有一堆课程可以选同一门课有“面授”和“网课”两种修读方式面授学分高但每学期面授名额有限。这里以“全选网课”为基准每门课的面授差值就是增量名额限制就是 K。和 Sake or Water 完全同构。变体二比赛出场策略。篮球比赛每个位置有两个球员可用A 球员防守好B 球员进攻好但 A 类型球员全场只能上一部分时间。假设每个位置的“基础评分”是 B 球员的评分A 球员比 B 球员多贡献的评分就是增量限制是 A 球员的总上场次数。解法同样是排序取前 K。变体三旅行交通切换。一个多天行程每天可以选择坐飞机或坐高铁飞机体验值高但里程有限高铁便宜不占额度。以全坐高铁为基准每天坐飞机的体验增量是飞机分 - 高铁分飞机天数受限时从大到小取增量即可。这三个变体来自不同场景但数学结构一模一样。我在实际训练中总结出一个快速识别方法只要题面里出现“每个东西有两种属性 / 两种选择 / 两种模式其中一种的使用次数有限制”并且每个选择的收益独立互不影响大概率就是差值贪心。4.3 快速判断口诀我自己编了一句口诀做题时先默念一遍先基线再差值排序取K正负要看清。展开解释就是“先基线”先把所有元素放到不占限制的那个状态算出 base。“再差值”把占用限制的状态的数值减去基线状态数值得到每个元素的增量。“排序取K”按增量从大到小排序在限制数量内取用。“正负要看清”检查题面是“最多 K”、“恰好 K”还是“至少 K”决定负增量到底要不要选。这句口诀不能替代理解但它能帮你在一分钟之内判断一道新题是不是这个套路。判断完再往深里想就很少会卡在第一步。5. 什么时候这套“排序贪心”会失效5.1 决策之间产生耦合时贪心立刻崩盘“Sake or Water”能排序取前 K本质上是因为每个场次的 d_i 彼此独立、互不相干。但很多变体题会把这个前提悄悄换掉。典型的反例是“清酒的快乐值递减”。比如第 i 杯清酒提供的基础分是 s_i但如果全场已经喝了 x 杯清酒那么第 i 杯清酒的实际价值变成s_i / x杯数越多每一杯的边际价值越低。这种情况下选不选第 i 场会影响后续每一杯清酒的价值d_i 不再是一个固定常量排序取前 K 的方法就完全失效。正确的方向可能是某种决策 DP或者利用单调性做更复杂的状态设计。另一个反例是“清酒组合加成”。如果第 1 场和第 2 场同时选清酒会额外加 10 分那么 d₁ 和 d₂ 就不再独立它们之间产生了正相关。排序单个增量时这种组合收益无法被体现直接贪心会漏掉最优解。这类耦合场景的处理本质上已经超出“差值贪心”的能力边界。判断的方法也很直接如果你发现选 A 的收益会因为你同时选了别的而改变那就不要套排序模板老老实实考虑 DP 或其他优化。5.2 收益函数不是线性相加时差值贪心的另一个隐含前提是“总收益等于各部分收益之和”。如果目标函数变成乘积或者要求计算某个区间的最大值之类的非线性结构base sum(delta)这个等式就根本不成立。举个例子如果目标是“总分 (喝清酒总美味值) × (喝水总清爽值)”这种乘积形式把某一杯从水换成清酒对结果的影响不仅取决于这杯本身的差值还取决于当前清酒和水的总量比例。排序单个增量无法刻画这种二阶效应只能退回到背包或更高级的优化框架。约束条件同样是重点。如果限制有两个维度比如“清酒最多 K 杯水也至少 M 杯”那光靠一维排序就不够了因为选清酒会连带影响水的数量。这种二维限制通常会逼迫你使用 DP 或费用流。我给出一道题能不能贪心的“三问检查”每个选择的收益是否独立不因其他选择而改变限制条件是否只影响选择数量不产生额外耦合最终目标是否等于所有选择收益的线性加和三个问题的答案都是“是”才放心使用排序贪心只要有一个是“否”就要考虑更复杂的模型。5.3 从 C 到 D 的难度跃迁出题人想考什么ABC 系列的 C 题一般默认考基础算法出题人故意把这道题放在 C 的位置就是在暗示不需要高级 DP不需要线段树只要你能看穿“二选一 上限”背后“默认方案 替换收益”的结构排序就能一步到位。但同样的故事如果搬到 D 题甚至 E 题通常就会加上前面说的耦合维度比如把 K 变成二维限制或者把每个场次分成清酒 / 水 / 都不喝三种状态。那时候需要的就不是简单的sort而是更贴合数据结构的优化。所以这道题除了教会我差值贪心更重要的是训练了“抽象出数学模型”的眼睛把看起来每个人都要单独决策的问题转化成“在一堆数字里选 Top K”。我个人在做这类题时的习惯是先不急着写代码先把题面改写一遍画出“哪些是固定贡献、哪些是可变贡献、限制消耗在哪个选择上”一旦这三个问题答清楚解法基本就浮出水面了。最后分享一点实际感受这类题最反直觉的地方恰恰是“先把所有项当作一种状态”这个举动看起来有点浪费甚至会让你觉得是不是在绕远路。但正是这个基准把模糊的“怎么选”变成了精确的“换哪一个更划算”。刷完Sake or Water之后我再去面对其他“二选一 次数限制”的题第一反应永远是先找基准、再算差值。这个小习惯帮我省下的时间远比想象中多。