1. 从“纪念品分组”到贪心算法的实战理解最近在带一些同学刷洛谷的题目发现P1094这道“纪念品分组”的题虽然被归在普及组但很多人在理解贪心算法的“为什么”和“怎么做”上还是容易卡壳。这道题本身描述很简单有一堆纪念品每个都有价格要把它们两两分组也可以单独一组要求每组的总价不超过一个给定的上限W目标是让总组数最少。很多人第一反应是排序后让最小的和最大的配对这就是所谓的“排序双指针”贪心。但为什么这个策略就是最优的如果让你手算验证或者遇到边界条件比如有多个价格相同的物品或者最大和最小无法配对时具体指针该怎么移动这些细节才是真正把算法思想转化为AC代码的关键。在我看来这道题是理解贪心算法“正确性证明”和“边界处理”的绝佳入门案例。它不像一些复杂的贪心需要复杂的数学推导其正确性比较直观但恰恰是这种直观容易让人忽略严谨的思考过程。今天我就结合这道题把贪心策略从直觉到证明再到代码实现的每一个环节掰开揉碎并分享一些在OJ上调试这类题目的实用技巧。无论你是刚开始接触贪心还是想巩固基础相信都能从中获得一些新的启发。2. 问题重述与贪心策略的直觉建立我们先抛开代码把洛谷P1094的问题用更生活化的方式描述一下。假设你是活动组织者采购了一批纪念品准备分发每件纪念品都有一个标价。现在你有一批包装盒每个盒子最多能装下总价值不超过W的纪念品。为了节省包装盒降低成本你希望尽可能让更多的纪念品共享一个盒子。规则是一个盒子最多放两件纪念品。你的任务就是找出最少需要多少个盒子。输入格式通常是第一行是盒子容量上限W第二行是纪念品数量n接下来n行是每个纪念品的价格。输出最少盒子数。最直接的暴力方法是枚举所有分组可能但n最大可以到30000这显然不可行。这时就需要观察规律寻找贪心策略。一个很自然的想法是如果想让盒子装得多就应该尽量让每个盒子“物尽其用”装到接近容量W。那么如果有一个很贵的物品价格高它单独放可能就占满一个盒子或者剩一点空间如果给它配一个便宜的物品把剩余空间利用起来就可能节省一个盒子。反之如果两个便宜物品凑一起虽然也能装满但它们可能本来可以分别去“搭配”更贵的物品从而更节省盒子。这引出了我们的核心贪心策略将纪念品按价格升序排序。每次尝试将当前最便宜的和当前最贵的配对。如果它们的总价不超过W就装进一个盒子然后同时考虑次便宜和次贵的如果总价超过W说明这个最贵的太贵了它跟谁配都会超至少跟当前最便宜的配会超那么它只能单独占一个盒子然后我们去考虑最贵的下一个即次贵的。这个策略为什么感觉是对的呢我们可以这样想最贵的物品A它只有两种命运1) 和另一个物品B配对2) 自己单独一个盒子。如果它能和当前最便宜的物品C配对成功那这就是对A最好的安排因为C是最便宜的给A留下了最大的配对空间即W-A的价格。如果连最便宜的C都配不上A那么A跟其他任何更贵的物品配对总价只会更高更不可能成功所以A注定要单独占一个盒子。对于物品C来说如果它能和最贵的A配对那它就被消耗掉了如果配不上它就去等待和“次贵的”物品配对。这个过程像是一个“匹配游戏”总是用最小的代价去“满足”当前最大的需求。3. 贪心策略正确性的严谨讨论直觉上合理但我们需要更严谨地说明这个贪心策略能得到全局最优解即盒子数最少。这里提供一个简单的证明思路有助于加深对贪心算法选取的理解。假设我们按价格升序排序后的数组为a[1...n]其中a[1]最便宜a[n]最贵。我们使用双指针i1左指针指向最便宜jn右指针指向最贵。命题上述贪心策略得到的解是最优的。我们可以用“交换论证”的思想来思考。假设存在一个最优解OPT。我们来看贪心解GREEDY与OPT的第一个不同的决策点。在贪心策略中对于最贵的物品a[j]如果a[i] a[j] W贪心会把它们配对。如果a[i] a[j] W贪心会让a[j]单独一组。现在考虑最优解OPT它如何处理a[j]情况1在贪心中a[i] a[j] W。假设在OPT中a[j]不是和a[i]配对而是和另一个物品a[k](i k j) 配对。因为数组已排序所以a[i] a[k]。那么在OPT中a[i]要么单独要么和另一个物品a[m]配对。我们可以构造一个新的解将OPT中的配对(a[j], a[k])和a[i]的安排交换变成(a[j], a[i])而a[k]去原来a[i]的位置。由于a[i] a[k]所以新配对(a[j], a[i])肯定不超过(a[j], a[k])的总价不会超限而a[k]被释放出来它可能可以和其他物品配也可能单独但最坏情况是和原来a[i]的安排一样。这样我们得到了一个盒子数不多于OPT的新解并且在这个决策点上与贪心一致。因此贪心在这个决策上不会比最优解差。情况2在贪心中a[i] a[j] W。那么a[j]只能单独一组。在OPT中如果a[j]居然和某个物品a[k]配对了那么由于a[i]是最小的有a[i] a[k]所以a[j] a[k] a[j] a[i] W这违反了容量限制矛盾。因此在OPT中a[j]也必须单独一组。通过以上分析贪心策略对当前最贵物品a[j]的处理方式至少可以调整到和某个最优解一致。然后我们可以用数学归纳法的思想将问题规模缩小排除掉已处理的a[j]和可能配对的a[i]对剩下的物品继续应用这个论证。最终可以得出结论贪心策略得到的解就是最优解。这个证明过程可能有点绕但其核心思想是贪心策略在每一步都做出了一个“安全”的选择这个选择至少存在一种方式可以导向全局最优解。对于入门者理解这个思路比死记硬背证明更重要。4. 双指针法的实现细节与边界处理理解了为什么这么做接下来就是如何用代码实现。核心是排序和双指针。我以最常见的C和Java为例拆解每一步并指出容易出错的地方。4.1 算法步骤拆解数据读取与存储读取W和n然后将n个纪念品价格读入一个数组或列表prices。排序对prices数组进行升序排序。这是贪心策略生效的前提。初始化指针与计数器设置左指针left 0右指针right n - 1盒子计数器count 0。双指针遍历循环条件为left right。如果left right说明只剩一件物品它必须单独一组count然后跳出循环。否则判断prices[left] prices[right] W。如果成立说明当前最便宜和最贵的可以装一盒。那么count同时left最便宜的用掉了right--最贵的也用掉了。如果不成立说明当前最贵的物品太贵无法和任何人配对至少无法和当前最便宜的配对。那么它必须单独一盒。count然后right--处理完了这个最贵的考虑次贵的。输出结果循环结束后count即为最少盒子数。4.2 关键代码实现C#include iostream #include algorithm #include vector using namespace std; int main() { int W, n; cin W n; vectorint prices(n); for (int i 0; i n; i) { cin prices[i]; } // 1. 排序 sort(prices.begin(), prices.end()); int left 0, right n - 1; int count 0; // 2. 双指针贪心配对 while (left right) { if (left right) { // 只剩一个单独一组 count; break; } if (prices[left] prices[right] W) { // 可以配对 count; left; right--; } else { // 最贵的单独一组 count; right--; } } cout count endl; return 0; }4.3 边界条件与易错点分析循环条件left right必须是小于等于。当left right时代表还有最后一个物品待处理需要进入循环为其分配一个盒子。如果写成left right会漏掉这个物品。left right的特殊处理在循环体内当左右指针重合意味着只剩一件物品。此时它无法配对必须单独占一个盒子。处理完后直接break跳出循环。这个判断放在循环开始处比较清晰。配对成功时的指针移动left和right--必须同时进行。因为这两个物品已经打包进一个盒子后续决策不再考虑它们。配对失败时的指针移动只移动right--。因为最贵的物品prices[right]单独成盒了所以右指针左移。左指针left不动因为最便宜的物品prices[left]还没被处理它可能能和下一个更便宜一点的贵物品配对。大数组与排序效率n最大30000使用O(n log n)的排序算法如C的sortJava的Arrays.sort()完全足够。不必担心性能。4.4 Java实现注意点Java的实现逻辑完全一致主要区别在于输入输出和容器。import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int W scanner.nextInt(); int n scanner.nextInt(); int[] prices new int[n]; for (int i 0; i n; i) { prices[i] scanner.nextInt(); } Arrays.sort(prices); int left 0, right n - 1; int count 0; while (left right) { if (left right) { count; break; } if (prices[left] prices[right] W) { count; left; right--; } else { count; right--; } } System.out.println(count); scanner.close(); } }注意在Java中使用Scanner读取大量数据时如果遇到性能问题通常本题不会可以考虑使用BufferedReader。但对于入门练习Scanner的简洁性更友好。5. 贪心算法的变体与思维拓展P1094是一个标准的、教科书式的贪心题目。掌握了它就掌握了“排序双指针”这类配对贪心的基本模式。但在实际竞赛或面试中问题可能会有所变化。理解核心思想后我们可以尝试解决一些变体这能极大锻炼思维能力。5.1 变体一每组最多装k件物品k2这是P1094的升级版。假设一个盒子最多能装k件纪念品k是一个给定的常数而不是两件。此时贪心策略还能用吗如何调整思路不再是最小配最大那么简单。一个常见的贪心策略是先装大的再用小的去填充剩余空间。具体可以这样将物品按价格降序排序先处理大的。遍历物品对于当前最贵的物品尝试寻找尽可能多的、价格较小的物品与之组合使得总价不超过W且物品数不超过k。这有点像“背包问题”但由于k通常不大我们可以用多重循环或更精细的贪心。实际上当k2时问题变得更复杂可能无法用简单的双指针贪心得到最优解有时需要借助动态规划或搜索。但如果是特例如k3可以设计特定的贪心规则。这提醒我们贪心算法不是万能的其正确性严重依赖于问题本身的性质。5.2 变体二求最大分组数每组至少两件这是另一个方向。假设我们不是要求盒子数最少而是要求在满足每组总价不超过W的前提下让尽可能多的组里包含两件物品即最大化“配对”的数量。盒子总数可能不是最少的但“成双成对”的盒子最多。这个问题其实可以用类似的贪心思路。排序后我们依然用双指针。但策略目标是“促成配对”。当prices[left] prices[right] W时我们当然配对。但当prices[left] prices[right] W时我们不能简单让right单独成组因为这样浪费了一次配对机会。此时我们应该尝试让right和left1、left2... 去配对吗这可能会退化成O(n^2)。一个更巧妙的思路是固定左指针用右指针向左寻找第一个能与之配对的物品。配对成功后左右指针都向内移动。如果找不到则左指针单独移动这个物品无法配对。这样能在O(n)时间内找到最多的配对。这个变体可以很好地训练我们对双指针灵活运用的能力。5.3 从“纪念品分组”到其他贪心问题“排序双指针”是贪心算法中一个非常经典的模板。它广泛应用于“两数之和”、“三数之和”、“最接近的三数之和”等数组类问题虽然那些可能更偏向于搜索或哈希。其核心思想是利用有序性系统地尝试边界组合从而避免暴力枚举。例如在“小船过河”问题POJ 1700中也有类似的贪心策略让最慢的两个人一起过河或者让最快的来回接送。其决策分析和本题有异曲同工之妙。多刷这类题目就能慢慢培养出对贪心策略的“感觉”。6. 调试技巧与OJ实战心得理论懂了代码写了提交上去可能还会遇到Wrong Answer或者Time Limit Exceeded。这里分享几个针对这类贪心题目的调试技巧和OJOnline Judge如洛谷实战心得。6.1 设计测试用例不要只依赖题目给的样例。自己构造一些有代表性的边缘数据最小规模n1。检查你的程序是否能正确处理单个物品。全部配对所有物品价格都很小任意两个相加都不超过W。理论上需要ceil(n/2)个盒子。例如 W10, n4, prices[1,2,3,4]。全部无法配对所有物品价格都很大任意两个相加都超过W。那么每个物品都需要单独一个盒子答案就是n。例如 W5, n3, prices[6,7,8]。混合情况穿插一些能配对和不能配对的。例如 W10, n5, prices[1, 9, 2, 8, 11]。注意有价格大于W的吗题目通常保证price W但最好确认一下。大量数据用脚本生成n30000的随机数据检查程序运行时间和结果是否合理例如盒子数不可能少于ceil(n/2)也不可能大于n。6.2 使用cout/printf或打印语句调试在不确定的时候在循环里打印出每一步left,right,count以及当前判断的两个价格prices[left]和prices[right]。这能帮你清晰地看到程序的决策过程快速定位逻辑错误。例如在C中while (left right) { cout left left ( prices[left] ), right right ( prices[right] ) endl; // ... 原有逻辑 }6.3 警惕输入输出格式洛谷的题目对输入输出格式要求很严格。确保你的程序只输出要求的结果不要输出任何额外的提示信息如“请输入W:”。注意换行。通常cout count endl;或printf(%d\n, count);即可。对于Java使用Scanner时注意nextInt()和nextLine()混用可能带来的换行符问题。本题简单读取数字一般没问题。6.4 性能优化对于本题30000的数据量O(n log n)的排序是瓶颈但完全可接受。如果n更大比如10^5就需要确保使用高效的排序。在C中std::sort是快排混合插排足够快。在Java中Arrays.sort()对于基本类型使用双轴快排对于对象使用TimSort也都是O(n log n)。双指针遍历部分是O(n)非常高效。这是贪心算法通常具备的优势——时间复杂度低。6.5 一个常见的思维陷阱先装小的有些同学可能会想既然要节省盒子是不是应该先尽量把小的装一起比如排序后从左到右遍历让相邻的两个小的先配对。我们来验证一下假设 W10, prices[1,2,7,8,9]。按“小配小”策略 (1,2)一盒(7,8)一盒9单独一盒共3盒。但按“小配大”策略 (1,9)一盒(2,8)一盒7单独一盒共3盒。结果一样再试一个W10, prices[1,9,9,9]。小配小(1,9)一盒剩下两个9各一盒共3盒。小配大排序后[1,9,9,9](1,9)一盒(9,9)超了不(1,9)配对后剩下[9,9](9,9)超W所以各一盒也是3盒。似乎一样但看这个例子W10, prices[2,3,8,9]。小配小(2,3)一盒(8,9)超W所以8一盒9一盒共3盒。小配大排序后[2,3,8,9](2,9)一盒(3,8)一盒共2盒可见“小配小”的策略不是最优的。它让两个小的“内部消化”了导致后面的大物品失去了配对机会。而“小配大”策略则保证了大的物品尽可能被“消化”掉减少了其单独成盒的可能。这个对比清晰地展示了贪心策略设计的重要性——不同的局部最优选择可能导致不同的全局结果。