第一次在题库里刷到 P1094 纪念品分组的时候我其实有点不以为然——排序、配对、统计组数看上去就是个普及组送分题。直到有次群里有人问这题的贪心到底凭什么是对的我才发现自己只能回答感觉上对根本讲不出严谨证明。于是我把这道题重新翻出来从题目约束到贪心思路从正确性证明到代码实现认真过了一遍。今天这篇文章就是那次复盘的结果适合已经把排序、数组、循环这些基础过完想彻底吃透双指针贪心这道经典题的读者。先给结论P1094 纪念品分组不是一个普通的排序后随便分的题它的核心是每组的容量上限只有 2正是这个限制让最贵的最便宜的配对成为最优策略。理解了这个限制代码其实也就二十行不到而理解了贪心为什么对你才能真正举一反三。1. 先把题目拆清楚每组最多两件总价还有上限题目背景是新年晚会的纪念品发放有一堆纪念品每个都有价格。现在要把它们分组每组最多包含两件纪念品并且每组的价格之和不能超过一个给定上限 w。要求是找出最少的分组数。把这个生活场景抽象成数学问题就是这样输入一个整数 w每组价格上限一个整数 n纪念品数量以及 n 个整数价格 a1, a2, ..., an。输出最小分组数。约束每组最多 2 个元素每组元素之和 ≤ w。数据范围方面w 最大到 30000n 最大到 30000。这意味着一个 O(n²) 的算法在极限数据下要跑大约 9 亿次运算基本会超时一个 O(n log n) 的排序再加一趟线性扫描才是这题的预期解法。这里最关键的一句话是每组最多包含两件。很多同学读题时容易把它忽略掉但恰恰是最多两件决定了整道题的解法走向。如果每组能放任意多件那问题就变成了一个类似装箱问题的 NP 难题根本不可能用一趟贪心解决如果每组必须恰好两件那又变成了另一个配对问题。正是最多两件这个宽松又受限的条件让最贵的配最便宜的这种贪心有了成立的基础。题目的样例是这样的输入 100 9 90 20 20 30 50 70 80 90 90 输出 6第一行的 100 是 w第二行的 9 是纪念品数量第三行是 9 个价格。手动想一下把 90 和 90 放在一组显然超了100 的上限摆在那里很多两两组合都放不进一组。所以输出是 6 组而不是更少。这个样例我会在下一节手动模拟一遍你会看到双指针是怎么一步步走出来的。还有个小细节值得注意题目里的每个纪念品价格本身不会超过 w。如果出现单件价格超过 w 的情况那这个纪念品连单独一组都放不了问题本身就无解了。正常数据不会这样设计所以算法里不用为这种情况单独写判断。真碰上了把它单独输出无解或者直接视为无法成组处理逻辑也不会和标准做法冲突。2. 贪心直觉从哪里来让最便宜的奖品去配最贵的奖品我自己第一次做这题时脑子里冒出来的第一个想法是把价格从小到大排序然后从两头往中间配对。这个直觉不是凭空来的它背后有两个非常直接的观察。观察一当前最贵的那个纪念品最需要一个搭档。每个组最多放两件而组的价格总和不能超过 w。那么最贵的纪念品想和别人凑一组就必须找一个便宜到足以填补剩余额度的搭档。如果它连最便宜的都搭不上那它就失去了和任何人配对的可能性。所以任何局面下先处理最贵的那个纪念品是逻辑上最迫切的。观察二最便宜的那个纪念品是万能低配。最便宜的纪念品和谁配对都有最大的成功可能因为它给搭档留出的价格余量最大。反过来想如果让一个不那么便宜的纪念品去陪最贵的可能也能成功但那个不那么便宜的原本可以和一个更便宜的配对从而腾出更贵的去配别人。换句话说让最贵的和最便宜的配对是在最大化后续配对的可能性。生活化地理解一下假设你和朋友去自助餐厅拼桌每桌最多坐两个人而且这桌的总战斗力不能超过某个上限。现在人群里有个最能吃的你肯定希望给他配一个最能省肚子的小鸟胃如果你给他配一个饭量一般的人可能两个人加起来就超预算了而那个小鸟胃又跑去陪了另一个人结果两头都浪费。所以算法就变得很自然了把所有价格从小到大排序。用两个指针 l 和 rl 指向当前最便宜的价格r 指向当前最贵的价格。每一轮只处理当前最贵的 r 指针指向的纪念品如果能和最便宜的 l 配对就让它们凑一组l 向右移动、r 向左移动组数加一如果不能和最便宜的 l 配对说明它和谁都配不了只能单独一组r 向左移动组数加一。重复直到 l 超过 r。这种用两个指针从两端向中间扫描的做法就是很经典的双指针贪心。每次只处理最贵的那一个要么找到搭档要么孤家寡人绝不拖泥带水。拿题目样例实际走一遍。排序后价格是20 20 30 50 70 80 90 90 90w 100。下面这张表是每一轮指针的变化轮次l 指向r 指向判断操作累计组数1209020 90 110 10090 单独一组r 左移12209020 90 110 10090 单独一组r 左移23209020 90 110 10090 单独一组r 左移34208020 80 100 ≤ 10020 和 80 一组l、r 同时内移45207020 70 90 ≤ 10020 和 70 一组l、r 同时内移56305030 50 80 ≤ 10030 和 50 一组l、r 同时内移6到第六轮结束后l 指向下标 3r 指向下标 2l r循环结束。答案是 6和样例输出完全一致。这个模拟过程可以看到一个很有趣的现象三个 90 元纪念品里前两个直接落单第三个和 80 元的那个拼成了最后一组。因为最贵的纪念品太多而便宜货不够用必然有多个贵价商品要独自成组。贪心做的就是在便宜货不够用的现实下尽量让每一个贵价商品都搭上一个便宜的从而把落单数量压到最小。这里顺便回应一个常见的直觉误区为什么不先让最便宜的两个配对比如把 20 和 20 配一组20 和 30 配一组这样做的问题在于你过早消耗了最便宜的万能选手。最便宜的东西应该用来解决最难解决的问题——也就是最贵的东西。让容易配对的两件先配对把难配对的两件留在后面很可能导致后面配不上组数反而变多。我待会儿在第 3 节里会用具体例子说明这种先易后难的做法差在哪里。3. 为什么贪心不会错一次挑不出毛病的交换论证很多 OI 选手对贪心题的态度是猜一个策略写代码交上去过了就完事。但 P1094 这道题我觉得特别适合拿来练习证明贪心正确性因为它的证明并不复杂而且能帮你建立信心真正理解了贪心为什么对考试时才敢放心用。为了证明方便我们把排序后的数组记为 b[0] ≤ b[1] ≤ ... ≤ b[n-1]当前要考虑的最便宜的是 b[l]最贵的是 b[r]。情况一b[l] b[r] ≤ w。按照贪心策略我们应该把 b[l] 和 b[r] 放在一组。问题是这样做一定不会让最终组数变差吗需要证明的是存在一个最优解其中 b[l] 和 b[r] 就在同一组。我们任取一个最优解来看如果 b[r] 本身就是单独一组的那很简单把 b[l] 从它原来的组里拿出来和 b[r] 凑成一组原来和 b[l] 一组的那个纪念品变成单独一组。原来两组现在还是两组组数不变而且新组 b[l] b[r] ≤ w 是满足约束的。如果 b[r] 和某个中间的 b[x] 在一组同时 b[l] 和某个 b[y] 在一组那么我们现在有两组(b[r], b[x]) 和 (b[l], b[y])。因为这两组都是合法的所以 b[x] b[r] ≤ w于是 b[x] ≤ w - b[r]。接下来做一个重新配队的交换让 b[l] 和 b[r] 组成一组让 b[x] 和 b[y] 组成一组。b[l] b[r] ≤ w 本来就是我们假设的条件没有问题。关键是 b[x] b[y] 会不会超过 w注意数组是有序的y 一定在 l 和 r 之间所以 b[y] ≤ b[r]。那么b[x] b[y] ≤ b[x] b[r] ≤ w这就证明了交换后的两组依然是合法的。组数没变但新的解里 b[l] 和 b[r] 已经在一起了。换句话说任何最优解都能在不增加组数的前提下调整为包含最便宜配最贵这个组合的最优解。贪心的这一步选择不可能把路走死。情况二b[l] b[r] w。这种情况下b[r] 和任意一个纪念品配对都会超限因为 b[l] 已经是最便宜的了最便宜的都配不上其他的更配不上。所以 b[r] 在任何一个可行解里都只能单独一组。贪心把它单独拎出来是唯一的选择当然也不会错。有了这两个情况的结论整个贪心的正确性就清楚了每一步处理后我们都可以声明这一步的结果与某个最优解一致然后把这个纪念品从问题里删掉剩下的子问题结构完全一样继续套用同样的推理。这就是数学归纳法的思路。这个证明里最漂亮的是那个交换论证。以前我看别的题解看到交换一下组数不变就直接跳过后来自己动手写才发现交换不是随便换的关键要把最贵的那个的搭档 b[x] 和中间那个 b[y] 放在一起并用b[x] b[r] ≤ w这个原始约束去夹住它。想明白这一步才算真正看懂了这道题的贪心。也许有人会问举几个例子对了不就能说明贪心对了吗不行。比如 w 100价格是 1、2、98、99。如果采用最便宜配第二便宜的策略1 和 2 配一组98 和 99 各自单独总共 3 组。但最优解是 1 99、2 98总共 2 组。所以先让容易配的配对这个直觉直接翻车而最贵配最便宜的贪心能稳定拿到最优解。这就是为什么要做严谨证明——反例往往藏在看起来很美的直觉里。4. 代码实现、复杂度与四个容易踩的坑证明归证明代码还是要落地。这题用 C 和 Python 写起来都非常短核心就是排序加双指针。先说 C 的实现#include bits/stdc.h using namespace std; int main() { int w, n; cin w n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); int l 0, r n - 1; int ans 0; while (l r) { if (a[l] a[r] w) { // 最便宜的和最贵的能凑一组 l; r--; } else { // 最贵的只能单独一组 r--; } ans; // 不管是哪一种情况组数都要自增 } cout ans endl; return 0; }Python 的版本逻辑完全一样w int(input()) n int(input()) a list(map(int, input().split())) a.sort() l, r 0, n - 1 ans 0 while l r: if a[l] a[r] w: l 1 r - 1 else: r - 1 ans 1 print(ans)复杂度方面排序是 O(n log n)while 循环每一轮要么移动 l、r 各一次要么只移动 r 一次总共最多执行 n 轮所以扫描部分是 O(n)。整体复杂度 O(n log n)。n 30000 时排序加扫描的运算量撑死几十万次在时间和空间上都是毫无压力的。哪怕 n 放到 10^6这个算法也能比较轻松地跑完。代码很简单但坑就藏在简单里。我见过周围不少新手在这四个地方翻车坑一while 循环条件写成了 l r而不是 l r。如果 n 是偶数l r 和 l r 结果一样但如果 n 是奇数排序后最中间的那个纪念品会没人处理。比如三个价格 20、70、90w 100用 l r 的话第一轮 20 90 10090 单独一组r 变成 1此时 l 0r 1l r 成立第二轮 20 70 90 ≤ 100两个一起处理l 1r 0循环结束答案是 2。看起来没问题。但换个例子100、200、300w 400l r 循环100 300 ≤ 400 配对l 1r 1循环条件不满足中间那个 200 被漏掉了答案是 1实际应该是 2。这就是问题所在。循环边界一定要写成 l r让最后剩下的单身纪念品也有机会单独成组。坑二ans 只写在配对成功的分支里忘了单独成组也要计数。有的同学写法是 if 配对成功时 anselse 只让 r 往左移、不加组数。这样最贵的那些落单的纪念品就显得消失了一样最后答案偏小。正确写法应该像我上面的代码那样不管进入哪个分支每一轮都代表处理掉了一个或两个纪念品组数无条件加一。坑三不排序直接开始枚举配对。双指针的前提是数组有序。如果不排序你无法保证 l 指向的是全局最便宜、r 指向的是全局最贵那么最便宜配最贵这个贪心依据就完全不成立了。还有一种做法是用嵌套循环暴力枚举每组配对复杂度 O(n²)n 30000 时直接超时。排序本身只是一个 O(n log n) 的操作这都嫌麻烦的话后面处理大规模数据会更麻烦。坑四输入格式读反。这道题的第一行是 w第二行是 n第三行才是价格列表。有同学一上来就读成第一行 n、第二行 w样例数据恰好可能结果显示碰巧能过几个点数据一放大就错。我的建议是写代码时先看清题目格式读入后可以在脑子里过一遍样例确认变量赋对了再继续。这个小习惯能省不少调试时间。还有个容易忽略的细节题目里 w 最大是 30000价格也是整数所以不存在浮点精度问题。组数最大值就是 n所有物品都单独一组用 int 完全够不用担心溢出。5. 举一反三同款双指针贪心还能解决哪些题目P1094 做完之后我最大的收获不是会了这一题而是发现这种排序 双指针 最值和最值配对的思路在算法题里是一个很有生命力的模板。最典型的就是力扣 881 救生艇Boats to Save People。题目背景是给出每个人的体重和一个救生艇的载重 limit每艘船最多坐两人问最少需要多少艘船。如果你把人换成纪念品把救生艇载重换成每组价格上限 w把限坐两人换成每组最多两件那这道题和 P1094 就是同一道题。解法一模一样按体重排序最轻的和最重的尝试同船超重就重的单独一艘否则两人同船。这道题的题号在力扣上比较有名评论区经常有人说这不就是 P1094 吗确实如此。再比如有一类题问的是数组里最多能组成多少对和不超过 K 的数对。思路同样是把数组排序然后 l 和 r 从两端开始扫能配就配。本质上这类问题的核心是最大化配对对数。为什么配对对数重要因为在 P1094 里每组能放 1 件或 2 件设配对对数为 p则组数 n - p每成功配对一对组数就比全部单独少 1。所以最小化组数等价于最大化配对对数。理解了这一层你就明白为什么双指针贪心追求的是尽量配对而不是优先把便宜的凑在一起。这个等价转换的思路值得多说两句。有些题目表面问 A实际上是在问 B而 B 才是贪心可以直接优化的对象。P1094 问的是最小分组数直接看分组数做贪心比较难切入但转换成最多配对对数策略就清晰了每一对配对都应该尽量节省资源而最节省资源的方式就是用最便宜的.去抵消最贵的。很多双指针贪心题都是这样把目标函数转换一下贪心策略就水落石出了。往更远处扩展这种从两端向中间逼近的模型还能处理一些变体。比如如果题目改成每组最多可以放 k 件k 2那情况就复杂了你还是希望用尽量少的组装下所有物品但每组超过两件之后最贵配最便宜就不再是最优策略因为一个组里可以塞下多个便宜的来平衡一个贵的这就变成了一个类似背包或装箱的问题复杂度会显著上升。P1094 之所以能用这么简单的贪心正是因为它把每组的容量压缩到了 2让问题的组合爆炸被直接规避掉了。遇到变种题时先确认每组最多几件、是否限重再决定用贪心还是 DP这是一条很重要的审题经验。回到 P1094 本身。我个人在实际刷题中的体会是做完一道贪心题别急着去刷下一道先花几分钟把贪心为什么是对的这个问题回答清楚哪怕只是用笔在草稿纸上画一画交换论证效果也比连做十道模板题要好。P1094 这个交换论证后来帮我在救生艇、配对类题目上基本一次过因为核心逻辑早就打通了。最后再分享一个小技巧写双指针循环的时候把每一轮循环看成处理当前必须处理的那个元素比如最贵的那个——要么给它找到一个搭档要么让它单独成组然后无条件让组数自增。这样写代码逻辑清晰也不容易漏计数。