贪心算法实战：士兵过河问题详解与C/Python/C++多语言实现 1. 项目概述从“士兵过河”到算法实战最近在带新人准备机试发现“士兵过河”这个经典问题出现的频率相当高。它不仅是华为OD机试的常客也是很多大厂笔试中检验候选人逻辑思维和编程基本功的试金石。题目本身描述很简单N个士兵要过河只有一条船船每次最多载2人过河速度由较慢者决定有的版本还要求必须有一个人把船划回来。目标是找到让所有士兵过河的最短总时间。听起来像是个小学奥数题但当你真正动手用代码去实现最优调度策略时就会发现里面藏着对贪心算法、动态规划乃至数据结构运用的深刻考察。网上能找到的很多解法要么只给个思路要么代码晦涩难懂对于正在备战的同学来说参考价值有限。所以我决定结合自己当年面试和后来多次复盘的经验把这个问题从问题分析、算法推导到C语言、Python、C三种语言的代码实现与对比彻底讲透。无论你是刚学完C语言基础想找题练手还是用Python刷题追求效率或是C面试需要展示功底这篇文章都能给你一份可以直接“抄作业”的实战指南。2. 核心算法思路拆解为什么不是简单的“最快来回送”拿到这个问题很多人的第一反应是让最快的士兵来回划船把其他人一个个送过去。我们来算一下假设士兵过河时间数组为[1, 2, 5, 10]。如果让耗时1的士兵来回送策略是1和2过(2)1回(1)1和5过(5)1回(1)1和10过(10)。总时间 215110 19。这个时间显然太长了。最优解其实是19分钟吗不对。一个更优的策略是1和2先过(2)1回(1)然后让最慢的两个人5和10一起过但需要让对岸第二快的人把船送回来。具体是5和10过(10)2回(2)最后1和2再过(2)。总时间 211022 17。比19少了2分钟。这里就引出了本题最核心的两种过河策略也是所有贪心或动态规划解法的基石2.1 策略A利用最快两人进行“摆渡”这种策略适用于最快的人速度优势非常明显足以承担多次往返的成本。最快(a[0])和次快(a[1])过河耗时 a[1]。最快(a[0])划船回来耗时 a[0]。最慢(a[n-1])和次慢(a[n-2])过河耗时 a[n-1]。次快(a[1])划船回来耗时 a[1]。 完成以上步骤对岸留下了最慢的两人本岸恢复了最快的两人。这“一趟”处理掉两个最慢的人所花费的时间是a[1] a[0] a[n-1] a[1] a[0] 2*a[1] a[n-1]。2.2 策略B利用最快的人进行“接驳”这种策略适用于最快的人和次快的人速度相差不大而最慢的两个人又非常慢的情况。与其让最快的人跑三趟不如让最快的人只跑一趟去接。最快(a[0])和最慢(a[n-1])过河耗时 a[n-1]。最快(a[0])划船回来耗时 a[0]。最快(a[0])和次慢(a[n-2])过河耗时 a[n-2]。最快(a[0])划船回来耗时 a[0]。 这“一趟”处理掉两个最慢的人所花费的时间是a[n-1] a[0] a[n-2] a[0] 2*a[0] a[n-1] a[n-2]。那么关键决策点来了在每一步我们如何选择用策略A还是策略B答案是每次需要送走当前剩余人员中最慢的两个人时我们比较两种策略的代价选择耗时更短的那个。即比较time_A a[0] 2*a[1] a[n-1]和time_B 2*a[0] a[n-1] a[n-2]取较小值。注意这个比较是动态的。随着最慢的两人被送走数组规模n在减小但a[0]和a[1]即当前最快和次快在策略A执行后是会回到本岸的因此它们在整个过程中是“稳定”的摆渡资源。而策略B则严重依赖最快的人a[0]的体力。2.3 边界情况与终结处理当最后剩下1、2、3个人时上述批量处理两人的策略不再适用需要特殊处理剩2人两人一起过时间取较慢者即a[1]假设数组只剩两个元素。剩3人最优方案是最快和次快过(a[1])最快回(a[0])最快和最慢过(a[2])。总时间 a[1] a[0] a[2]。也可以让最快分别送两个慢的过去但时间会更长。算法的主循环逻辑就是先将过河时间数组升序排序。然后只要人数大于3就循环比较两种策略选择代价小的累加时间并移除已过河的两个最慢的人。最后处理剩余2人或3人的情况。3. C语言实现贴近硬件思维的精细控制C语言的实现最能体现算法的原始过程和控制细节适合理解内存和循环操作。#include stdio.h #include stdlib.h // 比较函数用于qsort int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } int minCrossingTime(int times[], int n) { // 1. 安全性检查 if (n 0) return 0; if (n 1) return times[0]; // 虽然题目可能不出现但逻辑要完整 // 2. 排序升序最快的人在times[0] qsort(times, n, sizeof(int), compare); int totalTime 0; int remaining n; // 3. 主循环每次送走两个最慢的 while (remaining 3) { int a times[0]; // 最快 int b times[1]; // 次快 int y times[remaining - 2]; // 次慢 int z times[remaining - 1]; // 最慢 // 计算两种策略的代价 int strategyA a 2 * b z; // a,b过a回z,y过b回 int strategyB 2 * a y z; // a,z过a回a,y过a回 // 选择代价小的策略 if (strategyA strategyB) { totalTime strategyA; } else { totalTime strategyB; } // 送走了最慢的两个人剩余人数减2 remaining - 2; } // 4. 处理剩余的最后2人或3人 if (remaining 3) { // 剩余三人: a, b, c (已排序c最慢) totalTime times[0] times[1] times[2]; } else if (remaining 2) { // 剩余两人: a, b一起过 totalTime times[1]; // 时间取决于较慢者 } else { // remaining 1理论上不会在循环后出现除非初始n1 totalTime times[0]; } return totalTime; } int main() { // 测试用例 int soldiers1[] {1, 2, 5, 10}; int n1 sizeof(soldiers1) / sizeof(soldiers1[0]); printf(测试1 [1,2,5,10]: 最短过河时间 %d\n, minCrossingTime(soldiers1, n1)); // 应输出17 int soldiers2[] {1, 2, 3, 4, 5}; int n2 sizeof(soldiers2) / sizeof(soldiers2[0]); printf(测试2 [1,2,3,4,5]: 最短过河时间 %d\n, minCrossingTime(soldiers2, n2)); // 可自行计算验证 int soldiers3[] {5}; int n3 sizeof(soldiers3) / sizeof(soldiers3[0]); printf(测试3 [5]: 最短过河时间 %d\n, minCrossingTime(soldiers3, n3)); // 输出5 return 0; }C语言实现要点与避坑指南排序是前提qsort函数的使用是基础。务必确保传入的比较函数compare正确无误返回a-b实现升序。排序后times[0]和times[1]才始终是当前剩余人员中最快的两个。循环条件while (remaining 3)这是关键。为什么是大于3因为当剩余人数等于3时我们有一套固定的最优解法最快送两人不需要再套用两种策略比较。如果写成while (remaining 2)对于剩余3人的情况程序会尝试用策略去处理“两个最慢的人”但此时“次慢”和“最慢”其实是同一个人索引remaining-2和remaining-1可能指向同一个或相邻的值会导致逻辑错误或数组越界。索引与剩余人数remaining的联动在循环体内我们用remaining作为动态的“数组有效长度”。times[remaining-1]和times[remaining-2]总是当前最慢和次慢。每次循环后remaining - 2模拟最慢的两人已过河不再考虑他们。我们并没有物理删除数组元素只是改变了逻辑上的“终点”效率更高。边界条件处理main函数中的测试用例包含了多种情况经典案例、多人、单人。在机试中一定要自己设计这样的测试来验证代码鲁棒性。特别是n1的情况虽然题目可能保证n2但处理它能体现思维的严密性。4. Python实现简洁高效的问题求解Python的实现充分利用了其列表操作的便捷性和高级数据结构的表达能力代码更加清晰易懂。def min_crossing_time(times): 计算士兵过河最短时间 :param times: List[int]每个士兵的过河时间 :return: int最短总耗时 if not times: return 0 if len(times) 1: return times[0] # 1. 排序 times.sort() total_time 0 n len(times) # 2. 每次送走两个最慢的 while n 3: a, b times[0], times[1] # 最快和次快 y, z times[-2], times[-1] # 次慢和最慢 # 计算两种策略 strategy_a a 2 * b z # a,b过a回z,y过b回 strategy_b 2 * a y z # a,z过a回a,y过a回 # 选择更优策略并累加时间 total_time min(strategy_a, strategy_b) # “移除”已过河的两个最慢的人 times.pop() # 移除最慢的z times.pop() # 移除次慢的y n - 2 # 3. 处理剩余人员 if n 3: # 三人最快送两次 total_time sum(times) # 相当于 times[0] times[1] times[2] elif n 2: # 两人一起过 total_time times[1] # 取决于较慢者 else: # n 1 total_time times[0] return total_time # 测试与输出 if __name__ __main__: test_cases [ ([1, 2, 5, 10], 17), ([1, 2, 3, 4, 5], 16), # 可以手动验证1,2过(2),1回(1),4,5过(5),2回(2),1,2过(2),1回(1),1,3过(3) - 215221316 ([5], 5), ([1, 10, 11, 12], 24), # 1,10过(10),1回(1),1,11过(11),1回(1),1,12过(12) - 1011111235? 不对。用策略1,12过(12),1回(1),1,11过(11),1回(1),1,10过(10) - 1211111035。最优是1,10过(10),1回(1),11,12过(12),10回(10),1,10过(10) -10112101043? 更差。实际上对于[1,10,11,12]最优解是策略B两次2*a[0]a[2]a[3] 最后两人时间。先算送12,11: 2*1111225剩[1,10]时间10总35。但策略A呢送12,11: a[0]2*a[1]a[3]12*101233剩[1,10]时间10总43。所以选策略B总35。我们函数计算过程n43, a1,b10,y11,z12。strategy_a1201233, strategy_b2111225。选25total25移除12,11剩[1,10]。n2 total10最终35。但答案是24我们验证另一种全局最优是1和10过(10)1回(1)1和11过(11)1回(1)1和12过(12)。总1011111235。网上有些答案24可能是其他变种题目如不需要划船回来。我们算法逻辑是正确的。 ] for times, expected in test_cases: result min_crossing_time(times.copy()) # 使用copy避免原列表被修改 status 通过 if result expected else f失败预期{expected}得到{result} print(f输入{times}: 计算结果{result} [{status}])Python实现要点与心得列表的负索引与pop()方法times[-1]和times[-2]直接获取最慢和次慢代码非常直观。使用times.pop()和times.pop()来移除最后两个元素模拟最慢两人过河。这比C语言中操作索引更简洁但要注意这会修改原列表。在测试时我使用了times.copy()来避免影响后续测试用例这是一个好习惯。min()函数的内置优化直接使用min(strategy_a, strategy_b)来选择更优策略比写if-else更简洁。Python的内置函数通常经过高度优化效率有保障。循环条件与边界处理逻辑和C语言版本一致。当n3时sum(times)恰好等于abc代码更简洁。这种利用语言特性简化代码的能力在机试中能节省宝贵时间。测试驱动的开发在if __name__ __main__:块中构建测试用例集是调试算法的好方法。特别是包含边界值空列表、单元素和争议案例如上面的[1,10,11,12]能帮助你想清楚算法是否覆盖所有情况。对于[1,10,11,12]我们的算法输出35经过手动枚举验证这确实是“必须有一人划船回来”约束下的最优解。如果题目变种如船可以自己飘回来答案会是24但那已经是另一道题了。5. C实现平衡性能与工程化的选择C的实现可以兼顾C语言的性能和Python的抽象能力使用STL容器和算法代码既高效又清晰。#include iostream #include vector #include algorithm #include numeric // 用于accumulate using namespace std; int minCrossingTime(vectorint times) { // 输入检查 if (times.empty()) return 0; if (times.size() 1) return times[0]; // 1. 升序排序 sort(times.begin(), times.end()); int totalTime 0; int n times.size(); // 2. 贪心循环处理 while (n 3) { int a times[0]; // 最快 int b times[1]; // 次快 int y times[n - 2]; // 次慢 int z times[n - 1]; // 最慢 int strategyA a 2 * b z; int strategyB 2 * a y z; totalTime min(strategyA, strategyB); // 移除最后两个元素最慢的两人 times.pop_back(); times.pop_back(); n - 2; // 更新当前人数 } // 3. 处理剩余情况 if (n 3) { // 三人情况最快和次快过最快回最快和最慢过 totalTime accumulate(times.begin(), times.end(), 0); // 等价于 times[0]times[1]times[2] } else if (n 2) { totalTime times[1]; // 两人一起过时间取决于慢者 } else { // n 1 totalTime times[0]; } return totalTime; } int main() { // 测试用例 vectorvectorint testCases { {1, 2, 5, 10}, {1, 2, 3, 4, 5}, {5}, {1, 10, 11, 12} }; vectorint expected {17, 16, 5, 35}; for (size_t i 0; i testCases.size(); i) { vectorint timesCopy testCases[i]; // 拷贝因为函数会修改vector int result minCrossingTime(timesCopy); string status (result expected[i]) ? 通过 : 失败; cout 测试 i1 输入; for (int t : testCases[i]) cout t ; cout : 结果 result [ status ] endl; } return 0; }C实现要点与工程化思考使用vector和STL算法vectorint比原生数组更安全方便sort(times.begin(), times.end())一句完成排序。accumulate函数用于快速求和代码意图明确。这是C相比C语言在竞赛和面试中的优势。pop_back()的效率vector::pop_back()是O(1)操作用于移除最后两个元素非常高效。这与Python的list.pop()类似。注意我们通过n - 2来同步更新逻辑大小但times.size()在物理上确实减小了。如果后续代码还需要用times.size()需要注意这个变化。参数传递与拷贝函数minCrossingTime接收vectorint引用会修改原数组。在main函数测试时我创建了timesCopy来保存原始数据这是一个重要的细节。在实际机试环境中如果题目要求不修改输入你需要先创建一个副本或者调整算法不进行pop_back操作而是用索引控制。min()函数在std命名空间直接使用std::min比较两个策略代价。代码简洁性和可读性都很好。6. 三种语言实现对比与选择建议看完三种实现你可能会有疑问到底该用哪种语言准备华为OD机试这里我结合经验给你一些建议特性维度C语言实现Python实现C实现代码长度与简洁性较长需要手动管理索引和边界非常简洁列表操作和内置函数强大较为简洁STL提供了良好抽象执行效率高贴近硬件无额外开销相对较低但对于机试规模完全足够高STL经过优化性能接近C思维负担较高需仔细处理指针/索引和内存逻辑低更贴近自然的问题描述中等需熟悉STL容器和算法调试便利性一般依赖printf和调试器优秀交互式环境和清晰错误信息较好IDE支持完善华为OD机试适用性传统优势语言对底层理解要求高强烈推荐解题速度快易上手推荐平衡性能与开发效率学习成本高指针、内存管理低语法简单直观中高包含C语言基础加面向对象、STL给不同背景同学的建议如果你是算法新手或想快速上手刷题首选Python。它的语法让你能更专注于算法逻辑本身而不是语言细节。列表推导式、sort、min/max等内置函数能极大提升编码速度。在时间紧张的机试中这是巨大优势。如果你有C/C基础追求极致性能或目标岗位偏底层选择C。它既保留了C的性能又通过STL提供了Python般的便捷。vector、sort、min的组合足以应对大多数机试题。而且C是很多大型项目的开发语言掌握它对你长远发展有益。如果你的专业或项目经验以C语言为主可以用C。但要特别注意数组越界、指针错误等常见问题。在写代码时多画图理解索引变化多设计测试用例验证边界。一个关键提醒华为OD机试环境通常支持C/C/Java/Python/JavaScript等。在练习和考试时务必先确认题目对输入输出的格式要求。例如是连续输入多组数据还是单次输入输出是否需要特定格式我建议在你的代码模板里就写好标准的输入输出处理如C的scanf/printfPython的input().split()C的cin/cout避免考试时在这上面卡壳。7. 常见问题与深度扩展思考在实际编码和面试讨论中围绕“士兵过河”还会衍生出很多问题。这里我整理了几个最常见的并给出我的解答思路。7.1 如果船每次最多能载3人算法如何调整这是一个很好的扩展。当容量变为3时我们每次可以送走当前最慢的三个人。核心思路不变设计最优策略送走最慢的三人并让合适的快的人把船开回来。这需要分析更多种策略组合例如最快的一趟送两个慢的过去再回来接一个慢的或者最快和次快配合等。问题的复杂度增加但本质仍是贪心或动态规划比较不同策略组合的代价。在面试中面试官问这个问题更多的是考察你能否将解决原问题的方法论迁移到更复杂的情况而不是让你当场给出完美代码。你可以回答“我们需要重新推导送走最慢三人的最优子结构。可能涉及比较多种策略比如用最快的人分三次送或者最快和次快配合送等核心仍是比较这些策略的时间代价选择最小的。实现上可以将主循环条件改为while n 4假设有处理4人及以下的边界情况然后在循环内计算送走最慢三人的最优时间。”7.2 如何输出具体的过河步骤而不仅仅是总时间这是一个典型的“记录路径”问题。我们可以在计算总时间的同时用一个列表在Python中可以用list of tuples记录每一步的动作。例如记录(1, 2, ‘go’)表示1号和2号士兵过河(1, ‘back’)表示1号士兵划船回来。在代码中每当累加一种策略的时间时就将该策略对应的几步动作记录下来。最后总时间计算完毕步骤列表也同步生成。这要求你对两种策略每一步的人选都了如指掌。这个功能在调试时也非常有用可以验证你的算法是否按照你期望的方式在进行。7.3 动态规划(DP)解法是怎样的贪心解法一定最优吗对于原问题上述贪心解法已被证明是最优的。但我们可以用动态规划来理解它。定义状态dp[i]为送前i个最慢的士兵即times排序后从右数起的i个人过河所需的最短时间。那么状态转移方程就涉及我们讨论的两种策略dp[i] min(dp[i-2] strategyA_cost, dp[i-2] strategyB_cost)其中strategyA_cost和strategyB_cost的计算依赖于当前最慢的两个人以及最快的那两个人因为最快的人可能参与摆渡。实际上由于最快的两人是全局资源DP的状态设计可能需要调整。更严谨的DP会定义dp[i]为剩下的i个最快的人times[0…i-1]都未过河时的最短时间但这样状态转移会更复杂。贪心解法之所以有效是因为这个问题具有“贪心选择性质”和“最优子结构”。在面试中如果你能先给出贪心解法再提到“这个问题也可以用动态规划来思考状态dp[i]表示…”会显得你理解非常深刻。7.4 在机试中遇到变种怎么办华为OD或其他公司的机试题经常会在经典问题上稍作改动。比如船速固定船本身有速度士兵上船后过河时间取max(士兵速度船速)。这只需要在计算每次过河时间时用max(士兵时间船速)代替原来的士兵时间即可。有士兵不能划船某些士兵不会划船。这需要你在策略选择时保证划船回来的人必须是会划船的。这可能会改变最优策略因为“最快的人”如果不会划船就不能承担摆渡任务。求所有士兵过河的第k短时间这就变成了搜索问题BFS/DFS或使用更复杂的动态规划。应对变种的关键是彻底理解原问题的核心模型与算法推导过程而不是死记硬背代码。仔细阅读新题目的每一个约束条件分析它改变了原模型的哪个部分。基于原算法的框架进行修改。例如如果只是船速固定那么你只需要修改时间计算函数如果增加了划船限制你需要在选择策略时增加一个“划船资格”的判断。最后无论题目怎么变排序、贪心比较两种策略、处理剩余人数这三个核心步骤大概率仍然是解题的骨架。多练习多思考“为什么这样是最优的”你就能以不变应万变。