大厂OD机考题“荒岛求生”详解：排序+双指针求最少救生艇

最近身边好几个准备大厂OD机考C卷的朋友都在刷同一道题——“荒岛求生”，这名字听着像脑筋急转弯，实际是一个很标准的“救生艇最少数量”问题。第一次做的人很容易被题目描述绕进去，读题三分钟，最后发现核心就是一个排序加双指针。这篇就完整拆一下这道题的解法、五门语言的实现，以及机考实战里真正容易丢分的地方。

题目本身的价值在于：它同时考察了排序、贪心、双指针和边界条件，难度属于中等偏易，但想拿满分并不只是“写出AC代码”那么简单。无论你是刚刷题的新手，还是想用最短时间捡起多语言手感的老手，这篇文章都能直接当参考。

1. 荒岛求生到底在考什么：题目设定与考点拆解

1.1 一句话讲清题目

一群人被困在一座荒岛上，岸边有一条救生艇。救生艇有最大载重限制，而且为了安全，每条船最多只能坐两个人。每个人都有一个体重，现在需要把所有人数到安全区，求最少需要多少条船。

这里有两个硬性约束：

• 每条船的载重不能超过给定的limit；
• 每条船最多坐两人。

第二个约束特别关键，很多第一次做的人会忽略它，直接把问题当成“不限人数的背包容量问题”来做，结果整个贪心方向就跑偏了。

1.2 输入输出格式与示例

机考场景下，常见的输入格式是标准输入三行：

5 1 2 3 4 5 5

第一行是人数n，第二行是n个体重，第三行是船的载重上限limit。输出一个整数，表示最少需要的船数。

手工演算一下这个例子：

• 体重 1 和 4 可以坐一条船，总重 5；
• 体重 2 和 3 可以坐一条船，总重 5；
• 体重 5 单独坐一条船。

答案就是 3 条船。如果你直接把 5 单独算一条船，剩下的 1、2、3、4 都各自单独，那就得到 5 条船，明显不是最优。

1.3 这道题考察的四件事

这道题能在OD机考的C卷里反复出现，是因为它干净利落地覆盖了四件事：

• 排序的敏感性：体重不排序，后面一切贪心都是空谈；
• 贪心策略的选择：究竟怎么配船才能让船数最少；
• 双指针的代码实现：下标移动的边界条件非常容易写错；
• 边界思维：体重超限、空数组、只剩一个人等情况。

这四点决定了它非常适合做机考题：代码量不大，但细节密度高，很能筛选出“会写代码”和“能写好代码”的人。

2. 从人的直觉到算法直觉：贪心与双指针的由来

2.1 最容易想到的“先装满”方案为什么不对

很多人看到这道题的第一反应是：把所有人体重排序，然后让船尽量装满，最好每次载重都无限逼近limit。

这个直觉看似合理，但有一个致命问题：船有人数限制。就算两个人加起来离limit还很远，也不能再塞第三个人，所以“装满”这个概念在本题里并不成立。

还有个更隐蔽的误区：有人会想先安排最重的人，把剩下的最重的和最轻的凑一凑。如果实现方式不当，很容易多算船数。比如体重是[50, 49, 1, 2]，limit = 50，最优方案是 50 一条船、49+1 一条船、2 一条船，共 3 条。如果算法写成了“重的人优先单独坐，再回头看能不能补一个轻的人”，第一次就先把 50 单独送走了，后面 49 再配 1，最后 2 单独，结果也是 3。但换一组数据就可能出问题，所以不能靠这种临时拼凑的规则，得有一个稳定可靠的统一策略。

2.2 双指针是怎么一步步推出来的

正确的做法非常直白：先把所有体重升序排序，然后用两个指针，一个指向最轻的人，一个指向最重的人，每次处理最重的那个人。

为什么盯着最重的？因为最重的人一定有船坐，而且大概率是最难的“包袱”。我们先把它处理掉，后面的压力才会越来越小。

具体逻辑是这样的：

• 让最重的人和最轻的人尝试同船；
• 如果两个人加在一起不超过limit，那就让他们同船，两个指针同时往中间移动；
• 如果超过limit，说明最重的人和最轻的人都塞不进一条船，那最重的人只能单独坐一条船，只移动右指针；
• 每处理一次，船数加一。

循环结束条件要注意：当左右指针相遇时，剩下的那一个人也要单独坐一条船。

这个流程用一句话总结就是：每艘船先保证装下当前最重的人，能顺带捎上最轻的人就捎上，不能捎就让它单独走。

2.3 正确性直觉：为什么不担心“错过最优”

很多读者到这一定会问：为什么让最重的人和最轻的人配对就一定是最优？万一最轻的人跟别人配对更好呢？

这里有一个很直观的推理：

当前最重的人不管怎样都必须占用一条船。如果这条船能再坐一个人，我们选择最轻的人，一定不会比选择其他更重的人更差。因为最轻的人对载重空间的占用最小，等于把“最大的灵活性”留给了后面的配对。

反过来，如果最重的人和最轻的人都没法同船，那最重的人和任何人都没法同船，因为其他人的体重都不小于最轻的人，加在一起只会更重。

所以这个贪心策略在每一步都做了一个“不会被后续决策拖累”的选择。机考面试中能把这个直觉讲清楚，基本就够了。

2.4 复杂度：为什么只能排序一次

排序的时间复杂度是O(n log n)，双指针扫描部分是O(n)，总体复杂度就是O(n log n)。空间复杂度是O(log n)或O(n)，取决于排序实现。

这里想提醒一点：很多人会把双指针部分写成一个循环套循环的“找人配对”过程，导致时间复杂度退化成O(n^2)。在机考数据量比较温和时可能能过，但一旦n到达十万级别，超时是必然的。双指针的优美之处就在于，左右指针每个元素最多被访问一次，整个配对过程是线性完成的，完全不需要回溯。

3. 五种主流语言的实现与避坑

既然标题把 Java、Python、JS、C/C++、Go 五门语言都列出来了，那代码实现肯定要全覆盖。核心算法完全一致，主要差异集中在输入解析、排序 API 和语法细节上。

统一约定输入格式：第一行n，第二行n个体重，第三行limit。

3.1 Python 版本

import sys def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) weights = list(map(int, data[1:1 + n])) limit = int(data[1 + n]) weights.sort() i, j = 0, n - 1 boats = 0 while i <= j: if i == j: boats += 1 break if weights[i] + weights[j] <= limit: i += 1 j -= 1 boats += 1 print(boats) if __name__ == "__main__": main()

Python 版本最推荐用sys.stdin.read()一次性读取所有输入，然后用split()分割。机考的输入经常带多余空格和换行，这种方式最稳。

3.2 Java 版本

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] w = new int[n]; for (int i = 0; i < n; i++) { w[i] = sc.nextInt(); } int limit = sc.nextInt(); Arrays.sort(w); int i = 0; int j = n - 1; int boats = 0; while (i <= j) { if (i == j) { boats++; break; } if (w[i] + w[j] <= limit) { i++; } j--; boats++; } System.out.println(boats); } }

Java 的Arrays.sort(int[])对基本类型数组用的是双轴快排，性能足够。机考时类名注意写成Main，不然一些平台会找不到主类。

3.3 JavaScript 版本

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); const lines = []; rl.on('line', line => { lines.push(line.trim()); }); rl.on('close', () => { const n = parseInt(lines[0], 10); const weights = lines[1].split(/\s+/).map(Number); const limit = parseInt(lines[2], 10); weights.sort((a, b) => a - b); let i = 0; let j = n - 1; let boats = 0; while (i <= j) { if (i === j) { boats++; break; } if (weights[i] + weights[j] <= limit) { i++; } j--; boats++; } console.log(boats); });

JavaScript 最大的坑就是Array.prototype.sort()默认按字符串排序，不传比较函数就直接翻车。必须写成sort((a, b) => a - b)，数字数组才能正确升序。这行代码值两分。

3.4 C++ 版本

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> w(n); for (int i = 0; i < n; i++) { cin >> w[i]; } int limit; cin >> limit; sort(w.begin(), w.end()); int i = 0; int j = n - 1; int boats = 0; while (i <= j) { if (i == j) { boats++; break; } if (w[i] + w[j] <= limit) { i++; } j--; boats++; } cout << boats << endl; return 0; }

C++ 的sort在<algorithm>里，bits/stdc++.h是竞赛常用头文件，机考通常支持。如果平台比较严格，改成包含<iostream>、<vector>和<algorithm>三个头文件更稳妥。

3.5 Go 版本

package main import ( "fmt" "sort" ) func main() { var n int fmt.Scan(&n) w := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&w[i]) } var limit int fmt.Scan(&limit) sort.Ints(w) i, j, boats := 0, n-1, 0 for i <= j { if i == j { boats++ break } if w[i]+w[j] <= limit { i++ } j-- boats++ } fmt.Println(boats) }

Go 的fmt.Scan能自动处理空白符分隔的输入，比很多语言的输入解析都省心。sort.Ints就是为int切片准备的，不用额外写比较器。

3.6 语言差异小结

核心逻辑五份代码完全一致，差别只在语言惯用法。我的建议是：用你最熟的一门语言先把算法理解透，再顺手把另外四门语言的最小实现写一遍。多语言手感对机考帮助很大，因为不同卷子可能指定不同语言，临时切换时不至于手生。

4. 容易丢分的边界条件与输入解析

4.1 体重本身就超过 limit

题目通常会保证单个体重不超过limit，但保险起见，看到体重大于limit的人直接输出无法完成也是合理的。很多机考平台不会把这种异常数据放到测试用例里，不过写代码时心里要有一根弦。

如果你非要处理，可以在排序后先判断weights[n-1] > limit，直接输出一个异常值或者按题目约定处理。但一般情况下不要画蛇添足，题目说每个人都能上船，就按能上船处理。

4.2 空数组、单个元素

n = 0时输出 0，n = 1时输出 1。这两个 case 看起来简单，却是最容易在循环边界写崩的地方。

如果代码里写成while (i < j)而不是while (i <= j)，当n = 1时循环一次都不进，最后忘了补boats++，返回值就是 0。这种低级错误一旦出现，整题一分没有。

4.3 输入换行和分隔符的处理

机考输入有时候体重数组会跨多行，甚至每个体重单独一行。用Scanner、cin、fmt.Scan这类逐 token 读取的工具不用操心换行，但用 JavaScript 的readline或者 Python 的input()时就要小心。

Python 里最安全的做法就是sys.stdin.read().split()，不管输入长什么样，先把所有 token 拿到手里，再按位置分配。JavaScript 的lines数组如果遇到空行，lines[1]可能取不到，建议先把非空行过滤掉，或者用全部输入一次性split(/\s+/)。

4.4 while 循环里下标移动的经典坑

先看这段容易出错的写法：

while (i < j) { if (weights[i] + weights[j] <= limit) i++; j--; boats++; } if (i === j) boats++;

这个写法在大部分数据上是正确的，但在某些配对场景下，i和j会指向同一个已经被配对的元素，最后再加1就重复计数了。

举个例子：weights = [1, 2, 3, 4]，limit = 5。

• 第一次：1+4<=5，i=1，j=2，boats=1；
• 第二次：2+3<=5，i=2，j=1，boats=2；
• 循环退出，此时 i=2、j=1，i === j不成立，没问题。

但如果换成weights = [1, 1, 4, 4]，limit = 5：

• 第一次：1+4<=5，i=1，j=2，boats=1；
• 第二次：1+4<=5，i=2，j=1，boats=2；
• 退出后 i=2、j=1，也不成立，没问题。

真正有风险的是像[3, 3, 3]、limit=3这类数据。换成while (i < j)写法，第一次 3+3>3，j=1，boats=1；第二次 3+3>3，j=0，boats=2；退出后 i=0、j=0 相等，补 1，得到 3，正确。

但有些场景下配对完成后i会恰好等于j，而这个位置的人已经被分配了。为了避免自己绕晕，统一用while (i <= j)并在循环内显式判断i == j的写法，这是最清晰的。

5. 双机位机考实战：时间分配、自测与提交前检查

5.1 双机位环境是什么样

现在很多大厂OD机考都采用双机位监控：正面一个摄像头对着考生面部，侧后方一个摄像头对着桌面和屏幕。考试前通常会用手机扫码进入监考页面，然后按要求把手机放到侧后方支架上。

这个环境对写代码的影响主要有两点：

• 桌面必须清空，草稿纸和笔一般允许，但手机不能放在手边；
• 全程双手要出镜，不能趴着写字、不能频繁低头看键盘太夸张。

所以平时练习就要养成“直接看屏幕编辑代码”的习惯，不要依赖太多纸质草稿。机考编辑器通常没有本地IDE那么智能的补全和报错，提前适应裸写代码的状态很重要。

5.2 读题后的三分钟该做什么

拿到这道“荒岛求生”，我建议按这个顺序来：

1. 先把约束条件圈出来：每条船最多两人，载重上限是limit；
2. 想清楚输出是什么：最少船数，不是方案；
3. 在草稿纸或注释里写一句伪代码：排序、双指针、计数；
4. 确认输入格式，别把limit当成体重数组最后一个元素。

这三分钟做完了，后面的编码基本就是肌肉记忆。最怕的是题没读完就开始写，写到一半才发现还有“最多两人”这个条件，代码推倒重来，白白浪费时间。

5.3 必测的边界用例清单

写完代码不要急着提交，先在本地或编辑器里跑这几个用例：

第六个用例手算一下：6 个人体重全是 2，limit 是 4，每船最多两人，2+2=4，因此三艘船装满。如果代码输出 6，说明配对的i++逻辑丢了。

5.4 提交前的五步检查

提交之前，按下面这个清单过一遍，能减少绝大多数非技术性失分：

1. 确认没有多余的输出语句：机考只认标准输出，调试用的print、console.log全删干净；
2. 确认变量名没有拼写错误：排序、指针、计数各就各位；
3. 确认i和j的更新不会死循环：最好手工走一遍三个人体重相同的用例；
4. 确认输入的第三行正确解析：很多人在 limit 的读取上出错；
5. 确认语言选择正确：提交时平台会列出题目允许的语言，别用错版本。

这三分钟检查，比多写二十分钟优化代码更值钱。

最后再分享一个带人刷题时的体会：这道题我见过最快的同学十分钟写完，也见过有人卡在输入解析上半小时。它真的不难，难的是能不能稳定地把一件简单的事做对。如果你正在备考，建议把这类“排序+双指针”的题多刷几道，练到闭眼能写出代码的程度，机考时才能把时间留给后面更复杂的题目。