1. 项目概述什么是乘船问题在算法竞赛和编程面试中有一类问题因其巧妙的贪心思想而成为经典它就是“乘船问题”。我第一次遇到这个问题是在准备一场算法比赛时题目描述很简单有n个人每个人的体重是已知的现在需要安排他们乘坐若干艘船过河。每艘船有最大载重限制并且最多只能坐两个人。目标是找出最少需要多少艘船才能让所有人都过河。这听起来像是一个简单的组合问题但当你真正开始动手写代码时会发现里面有不少细节需要处理。比如最重的人如果找不到合适的搭档就必须独占一艘船又比如如何高效地配对避免使用暴力搜索导致超时。这个问题完美地体现了贪心算法的核心——“在每一步选择中都采取当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的”。它不仅是C算法学习的绝佳练手题更是理解“排序双指针”这一经典解题范式的敲门砖。网上能找到的代码很多但要么注释不清要么边界条件处理得不够优雅。今天我就结合自己多次实现和教学的经验拆解一份我认为最清晰、最健壮、也最易于理解的C模板代码。这份代码不仅可以直接用于解决原题其背后的思想也能灵活应用到其他类似的“两两配对求最优解”的场景中比如“两数之和”的变种、任务调度等。无论你是正在刷题的信息学奥赛选手还是准备技术面试的求职者掌握这个模板都大有裨益。2. 核心思路与贪心策略解析2.1 问题建模与关键约束首先我们把问题用更严谨的语言重新定义一下输入一个整数n表示人数一个整数数组weights存储每个人的体重一个整数limit表示每艘船的最大载重。约束一艘船最多载两人且两人的体重之和不能超过limit。目标计算将所有n个人运过河所需的最少船只数量。这个问题的关键在于“最多两人”这个限制。如果一艘船能坐无限多人那就变成了一个背包问题。正因为只能坐两人它才具备了使用贪心策略高效求解的可能性。2.2 贪心策略的推导与证明最直观的贪心策略是什么呢我们可以从“最重的人”入手考虑。假设我们已经将所有人按体重从轻到重排序。策略核心总是尝试让当前最重的人与当前最轻的人配对。为什么这是正确的必要性如果最重的人记为people[r]都无法和最轻的人记为people[l]同船即people[l] people[r] limit那么people[r]和任何其他人同船都会超重。因此people[r]必须独自乘坐一艘船。这是唯一的选择。最优性如果最重的人可以和最轻的人同船people[l] people[r] limit那么这种配对方式“物尽其用”为剩下的中间体重的人留下了更多的配对可能性。因为最轻的人是最有可能与最重的人成功配对的如果连他都不行那最重的人就注定要单独乘船。如果可行那么让最轻的“消耗品”去搭配最重的“难题”是一种全局最优的决策。这个策略可以用“双指针”技巧高效实现。左指针l指向当前最轻的人右指针r指向当前最重的人。通过移动这两个指针我们可以在一次遍历O(n)内完成所有配对决策。注意贪心算法的正确性并非总是显而易见。对于乘船问题其正确性可以通过“反证法”或“交换论证”来严格证明。简单来说如果存在一个最优解其配对方式与我们的贪心策略不同我们总可以通过一系列“交换”操作将其调整为贪心策略的解且不会增加船只数量。这证明了贪心解至少和最优解一样好。2.3 算法流程与复杂度分析基于以上策略完整的算法流程如下排序将体重数组weights按升序排序。这是贪心策略生效的前提时间复杂度为 O(n log n)。初始化设置左指针l 0右指针r n - 1计数器boats 0。双指针遍历当l r时循环如果l r说明只剩一个人他需要一艘船。boats然后退出循环。否则检查weights[l] weights[r] limit。如果成立说明最轻和最重的可以同船。boats然后l最轻的上船了r--最重的也上船了。如果不成立说明最重的人必须独自乘船。boats然后r--最重的人上船最轻的留下等待下次配对。返回结果循环结束boats即为所需的最少船只数。时间复杂度主要消耗在排序步骤为 O(n log n)。双指针遍历是 O(n)。因此总复杂度为 O(n log n)对于 n 高达 10^5 的数据规模也完全可行。空间复杂度如果排序是原地进行的如使用std::sort则为 O(1)。如果输入数据不可修改则需要 O(n) 的额外空间来存储排序后的副本。3. 模板代码逐行精讲与避坑指南下面是我打磨了无数遍的C模板代码。它不仅正确更注重可读性和健壮性。#include iostream #include vector #include algorithm using namespace std; int minBoats(vectorint weights, int limit) { // 1. 边界检查如果没有人不需要船 if (weights.empty()) return 0; // 2. 关键步骤排序 sort(weights.begin(), weights.end()); int left 0; // 指向最轻的人 int right weights.size() - 1; // 指向最重的人 int boats 0; // 3. 双指针贪心匹配 while (left right) { // 情况1只剩一个人左右指针重合 if (left right) { boats; break; // 这个人必须单独一艘船处理完后循环结束 } // 情况2最轻和最重的人可以同船 if (weights[left] weights[right] limit) { boats; // 用一艘船装下这两个人 left; // 最轻的人已安排 right--; // 最重的人已安排 } // 情况3最重的人无法与任何人同船至少无法与最轻的同船 else { boats; // 最重的人单独一艘船 right--; // 安排最重的人 // 最轻的人(left)不动留待下一轮尝试 } } return boats; } int main() { // 示例输入 vectorint weights {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int limit 10; int result minBoats(weights, limit); cout 最少需要船只数量: result endl; // 更复杂的测试用例 vectorint weights2 {3, 5, 3, 4}; // 体重为[3,3,4,5] limit 5; // 贪心过程[3,5]不能同船(85)5单独一船 - [3,4]可以同船(75? 不75 3475不能同船) // 等等这里有个陷阱排序后是[3,3,4,5]limit5。 // 正确配对5单独一船4单独一船(因为4375)两个3各需一船不对两个3可以同船(3365? 65不能)。 // 所以需要4艘船。让我们用函数验证。 result minBoats(weights2, limit); cout 测试用例2最少需要船只数量: result endl; // 预期输出 4 return 0; }3.1 代码关键点解析与易错点排序是基石sort(weights.begin(), weights.end())这行代码是算法的核心。没有排序双指针贪心策略就无从谈起。务必确保在操作前进行了排序。循环条件left right使用而不是是为了处理最后只剩一个人的情况left right。如果使用当最后剩一个人时循环会直接退出导致漏数一艘船。left right的特殊处理在循环内部优先判断left right是一种清晰的写法。它明确地处理了边界情况当只剩下一个人时他无论如何都需要一艘船计数后直接跳出循环。你也可以将其合并到后面的判断中但这样写逻辑更分明。if (weights[left] weights[right] limit)的判断这是贪心决策点。注意是等于极限重量也是可以同船的。指针移动逻辑可同船时 (left,right--)两个人都被安排指针向中间移动。不可同船时 (right--)只有重的人被安排单独一船轻的人指针left不动。这是新手最容易出错的地方如果此时也left就错误地“跳过”了那个轻的人他可能还能和下一个稍重的人配对。输入验证函数开头对空向量的检查是良好的编程习惯虽然在这个问题里可能不是必须的。3.2 常见错误与调试技巧错误结果总是偏少最常见的原因是循环条件用了while (left right)且没有正确处理left right的情况。或者是在重的人单独乘船时错误地将left也移动了。错误结果偏多检查排序是否正确或者是否在可同船的情况下只移动了一个指针。调试建议在循环内添加打印语句实时查看left,right,weights[left],weights[right],boats的值。用一个小规模的手算案例比如上面main函数中的weights2来验证是最快的方法。实操心得我强烈建议在写这类双指针贪心算法时先在纸上画两个箭头手动模拟一遍过程。用一组具体数据比如[1,2,3,4,5,6], limit6一步步走流程。这能帮你彻底理解指针移动的每一个细节远比死记硬背代码有效。4. 模板的变种与扩展应用经典的乘船问题模板之所以强大在于其思想可以迁移到多种变体问题中。理解核心后你就能举一反三。4.1 变种一每艘船有固定容量CC2如果每艘船最多可以坐C个人而不仅仅是2个问题就变成了一个更复杂的贪心或动态规划问题。经典的“双指针”策略不再直接适用。一种常见的贪心思路是依然先排序。尝试用一艘船装下当前最重的一个人以及尽可能多的最轻的人从最轻的开始尝试装入直到达到人数上限或重量上限。这需要在内层使用另一个指针或循环来“装填”轻的人。 这种方法在C不大时是有效的但并不总是最优。对于更大的C可能需要用到“背包问题”的思路或更复杂的搜索。4.2 变种二求方案而非仅数量如果题目要求输出具体的配对方案即哪两个人上了同一艘船我们只需要在模板代码中增加一个数据结构来记录。在可同船的分支里 (if (weights[left] weights[right] limit))将weights[left]和weights[right]作为一个 pair 存入一个列表如vectorpairint, int。在重的人单独乘船的分支里将weights[right]单独存入另一个列表或用一个特殊值如-1表示单人船。 这样在计算数量的同时也完成了方案的构建。4.3 扩展应用LeetCode “两数之和小于等于目标值”的计数问题LeetCode 上有一类问题给定一个数组和一个目标值target计算有多少个数对的和小于等于target。这简直就是乘船问题的“计数版”。 解决方案完全一样排序数组。使用双指针l和r。如果nums[l] nums[r] target那么对于这个固定的nums[r]所有从l到当前r之间的数包括l都能和它组成有效数对不对。更准确的计算是当nums[l] nums[r] target时对于当前的l和r数对(nums[l], nums[r])是有效的。但为了计算所有数对我们需要一个不同的计数逻辑。实际上更高效的计数方法是当nums[l] nums[r] target时说明从l到r之间的所有数因为数组已排序与nums[l]配对都能满足条件不应该是(l, r)这个配对本身满足。要计算所有配对通常的套路是固定l找到最大的r使得nums[l] nums[r] target那么对于这个l有(r - l)个有效的数对(l, l1), (l, l2), ..., (l, r)。然后l继续寻找新的r。这个过程依然是 O(n) 的。可以看到核心的“排序双指针”框架是相通的只是根据具体问题调整指针移动和计数的逻辑。5. 性能优化与边界条件深度测试一份健壮的模板代码必须经得起各种极端输入的考验。我们来设计一些测试用例并看看我们的实现表现如何。5.1 极端测试用例设计最小输入weights [], limit 100。预期输出0。我们的代码开头有if (weights.empty()) return 0;能正确处理。weights [50], limit 50。预期输出1。循环中left right分支会处理。所有人必须单独乘船weights [100, 200, 300], limit 150。排序后为[100, 200, 300]。第一轮100300400 150300单独一船。第二轮100200300 150200单独一船。第三轮只剩100单独一船。总计3艘船。代码逻辑会一步步执行这个过程。所有人都可以两两配对weights [40, 50, 60, 70], limit 110。排序后[40, 50, 60, 70]。第一轮4070110 110同船。第二轮5060110 110同船。总计2艘船。体重存在重复值weights [80, 80, 80, 80], limit 160。排序后不变。第一轮8080160 160同船。第二轮8080160 160同船。总计2艘船。算法完全能处理重复值因为排序后它们相邻双指针逻辑不受影响。极限重量weights [limit, limit, limit, limit], limit 100。即所有人体重都等于船限。第一轮100100200 100最右的100单独一船。后续同理每个人都需要单独一船。总计4艘船。weights [limit-1, limit-1, limit-1, limit-1], limit 100。体重均为99。第一轮9999198 100不能同船所以每个人都需要单独一船。这提醒我们不能想当然地认为两个小于 limit 的数相加就一定小于等于 limit。5.2 潜在优化点分析我们当前的算法时间复杂度是 O(n log n)空间复杂度是 O(1) 或 O(n)。这已经是这个问题最优的复杂度级别了因为排序的复杂度下限就是 O(n log n)。在 n 很大10^5时排序是主要开销。如果体重范围很小例如题目明确说明体重是1到100之间的整数。我们可以使用计数排序将排序复杂度从 O(n log n) 降低到 O(n K)其中 K 是体重范围这里是100。这在某些极端情况下可以带来常数级别的优化但通常std::sort的快速排序实现已经非常高效对于通用情况是首选。内存优化如果输入数据量极大且内存敏感且允许修改输入数组那么原地排序的std::sort是最佳选择。我们的模板代码使用了引用传递vectorint避免了不必要的拷贝。注意事项在在线判题系统OJ中除非特别说明否则不要轻易尝试替换std::sort。它的实现经过了高度优化在绝大多数情况下都是最快的。盲目使用计数排序等可能因为初始化计数数组的开销反而更慢。6. 从乘船问题到贪心算法的思维训练乘船问题是一个绝佳的贪心算法教学案例。通过它我们可以提炼出应用贪心算法解题的一般步骤问题特征识别问题具有“最优子结构”吗当前的选择是否会影响后续子问题的结构乘船问题中让最重和最轻的配对或单独走剩余的人构成了一个规模更小的、性质相同的子问题。贪心选择策略找出每一步的“局部最优”选择是什么。在这里局部最优就是“尽可能让船装满”即优先解决最重的人的过河问题并尝试用最轻的人去搭配他。证明正确性或理解其正确性这是最关键也最难的一步。对于乘船问题我们通过“最重的人必须与最轻的人配对尝试”这一推理来理解其正确性。在面试或学习中即使不能严格证明也要能清晰地阐述这个推理过程。实现与验证将策略转化为代码并用多种测试用例验证。掌握这个思维流程你就能尝试解决更复杂的贪心问题例如“区间调度问题”选择最多不重叠区间、“霍夫曼编码”、“最小生成树Prim/Kruskal算法”等。它们的核心思想都是通过一系列局部最优选择期望达到全局最优。最后我再分享一个调试贪心算法的小技巧当你对贪心策略的正确性存疑时可以尝试构造一个“反例”。即思考在什么情况下你的局部最优选择会导致全局结果变差。如果你无法构造出这样的反例那么你的策略很可能是正确的当然这不能替代严格证明。对于乘船问题你可以试着想不让最重的人和最轻的人配对而是让他和另一个中等体重的人配对会不会得到更少的船通过推理你会发现这要么不可能要么不会比贪心策略更好。这份关于乘船问题的C模板代码和背后的思考就分享到这里。代码虽短但蕴含的贪心思想和双指针技巧却是算法学习中不可或缺的基石。希望下次你再遇到类似“两两配对”、“最小化组数”的问题时能立刻想起这个经典的模型和清晰的解法模板。