POJ 1700快速渡河问题：贪心策略经典解析与实现

POJ 1700 的快速渡河问题，很多人第一次见到时都以为是一道模拟题：几个人过河、船一次载两个、还得有人把灯送回来，套个循环不就行了？结果一提交就是错。我第一次做这题时也一样，后来才意识到，这题考的根本不是模拟，而是贪心策略里最经典的一类——局部决策会直接影响全局代价，所以你每一步都必须从两种方案里挑那个更省的。这篇文章就把这道题从头到尾拆开讲清楚，包括两种策略为什么存在、每轮决策怎么算、代码怎么写、边界条件怎么处理，以及我实际调试时踩过的几个坑。不管你是刚接触贪心的新手，还是准备复习经典题的选手，这篇都能直接用。

1. 题目本质与贪心直觉

1.1 题目到底在说什么

先把题目规则还原一下：有 n 个人在河的一侧，要到另一侧去。河边有一条船，每次最多坐两个人，船过河需要的时间等于船上两个人的过河时间中较慢的那个。晚上过河必须带一盏灯，而灯只有一盏，所以每次有人过去之后，如果还有人留在起点，就必须有一个人把灯送回来。要求的是所有人全部到达对岸所需的最短总时间。

这个规则里最容易忽略的就是“送灯”这一步。很多人一开始想的是：最快的人来回接送不就行了？确实，这是最朴素的想法，但也是最容易掉进去的坑。

题目给了一个很经典的例子：四个人过河，时间分别是 1、2、5、10。如果只让 1 号最快的人来回接送，流程是：1 带 10 过去，耗时 10；1 回来，耗时 1；1 带 5 过去，耗时 5；1 回来，耗时 1；1 带 2 过去，耗时 2。总耗时 19。但实际最优解是 17，做法完全不同：1 和 2 先过去，耗时 2；1 回来，耗时 1；5 和 10 过去，耗时 10；2 回来，耗时 2；1 和 2 再过去，耗时 2。总耗时 17。

为什么多走了一趟，反而更省？这就是这道题的核心。

做这道题之前，先把所有人的过河时间按从小到大排序。设排序后的数组为 a[0] 到 a[n-1]，那么 a[0] 是最快的，a[1] 是第二快的，a[n-1] 是最慢的。这道题所有贪心决策都建立在有序数组上，排序是第一步，也是最重要的一步。

1.2 为什么“每次都让最快的送”不是最优

直观上，让最快的人当“摆渡人”确实有道理：他速度快，回程耗费的时间最少。但问题出在他接力的对象太慢。当最快的人带着最慢的人过河时，这一趟的耗时完全由最慢的人决定，比如 1 带 10 要花 10 分钟。接着最快的人还要回来，再带次慢的人过去，又要花掉一个很长的耗时。也就是说，最快的人虽然自身快，但他被迫陪着最慢的人“慢”了两次，代价非常大。

而第二种策略聪明在，它让最快的两个人先打配合：1 和 2 先过河，2 的耗时虽然比 1 慢一点，但也就多 1 分钟；然后 1 回来；接着让 5 和 10 这两个最慢的人一起过河，反正他们单独过也是 10 分钟，一起过还是 10 分钟；最后让 2 回来接 1。这样一来，最慢的两个人只用了一趟就同时过河，等于把“10 分钟”这个昂贵代价用了一次就解决了。

所以这道题的关键不是“谁最快谁就一直跑”，而是“怎么把最慢的人尽量打包送走，同时让回程的代价最小”。理解了这一点，贪心策略就呼之欲出了。

1.3 核心建模：一轮送走两个人

做这道题要换一个思路：不要一次考虑一个人，而是把“处理掉当前最慢的两个人”当成一轮操作。每次我们从剩下的未过河的人里，找出最慢的 a[n-1] 和次慢的 a[n-2]，想办法把他们送到对岸。因为这两个人无论怎么安排，都必须过河，而且他们过河的那一趟耗时基本是确定的——至少是 a[n-1]。问题在于，为了把灯送回起点，需要让谁在中间跑回来。

每送走这两个最慢的人，剩余人数就减少两个。然后继续处理新的最慢的两个人。等到剩余人数变成 2 或 3 时，问题就变得非常简单，直接按公式处理即可。

这样建模之后，问题就从“n 个人一起过河”变成了“每一轮用最小代价送走两个最慢的人”，而每一轮的最优决策，就在两种固定模式里选一个。这就是贪心策略的骨架。

2. 两种策略的推导与取舍

2.1 策略A：最快者来回护送

策略 A 就是很多人第一反应想到的方案：让最快的人 a[0] 负责接送最慢的两个人。具体流程是这样的：

• 第一步：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[0] 还在起点，剩余人数减少 2。这一轮的代价是：

tA = 2 * a[0] + a[n-1] + a[n-2]

以 [1, 2, 5, 10] 为例，tA = 2 * 1 + 10 + 5 = 17。注意这 17 只是“送走 5 和 10”这一轮的代价，还没算最后剩下的 1 和 2 过河的时间。

策略 A 的适用场景是两个最慢的人耗时差距很大、或者第二快的人速度也不快的时候。比如一组数据是 [1, 9, 10, 11]，tA = 2 + 11 + 10 = 23，这个代价还算合理。

2.2 策略B：双快车手接力

策略 B 就是前面例子里的巧妙方案：让最快的两个人先过去，把灯送回来一个，然后让最慢的两个人一起过去，再由另一个较快的人把灯送回来。具体流程：

• 第一步：a[0] 和 a[1] 先过河，耗时 a[1]；
• 第二步：a[0] 把灯送回起点，耗时 a[0]；
• 第三步：a[n-1] 和 a[n-2] 一起过河，耗时 a[n-1]；
• 第四步：a[1] 把灯送回起点，耗时 a[1]。

这一轮结束之后，最慢的两个人都到了对岸，a[0] 和 a[1] 也回到了起点，剩余人数同样减少 2。这一轮的代价是：

tB = a[0] + 2 * a[1] + a[n-1]

还是以 [1, 2, 5, 10] 为例，tB = 1 + 2 * 2 + 10 = 15。加上最后 1 和 2 过河的 2 分钟，总耗时 17。

策略 B 的核心思想是：与其让最快的人陪着最慢的人慢吞吞过两次河，不如让最快的两个人配合，用“两个较快的人分别跑一次回程”来替代“最快的人跑两次回程”。代价是 a[1] 多跑了一趟，但省下了 a[0] 陪最慢者过河的那一趟。

2.3 每轮决策：取两者较小值

每轮到底选 A 还是选 B，不是凭感觉，而是直接比较两个公式的大小，取较小值：

tA = 2 * a[0] + a[n-1] + a[n-2]

tB = a[0] + 2 * a[1] + a[n-1]

写成代码就是：

ans += min(2 * a[0] + a[n-1] + a[n-2], a[0] + 2 * a[1] + a[n-1]);

两个公式做差，可以得到一个更有指导意义的判断式：

tA - tB = a[0] + a[n-2] - 2 * a[1]

也就是说，当 a[0] + a[n-2] > 2 * a[1] 时，策略 B 更优；否则策略 A 更优。这个差值很直观：如果第二快的人足够快，策略 B 的“接力跑”优势就大；如果次慢的人和第二快的人速度差不多，那么让最快的人来回送反而更省。实际写代码时不需要自己判断，直接取 min 就行，但理解这个差值能帮你判断一组数据应该走哪种方案。

2.4 贪心正确性直观说明

有人会问：每轮都取这两种策略的较小值，为什么一定能得到全局最优？这一步需要稍微想一下。

当前最慢的 a[n-1] 和次慢的 a[n-2] 无论如何都要过河。他们过河那一趟的耗时下限是 a[n-1]，这是省不掉的。唯一能优化的，就是在这两人过河前后，灯怎么送回起点。灯要回起点，必须要有一个已经在对岸的人再划回来。那么，在“送走这两个最慢的人”这个局部目标下，合理的送灯模式其实只有两种：要么最快的人来回跑，要么最快的两个人配合跑。任何更绕的方案，都可以化简成这两种之一，而且不会更优。

另外，每一轮送走的是当前最慢的两个人，这个过程和之前已经送走的人无关，也不会影响剩余人的相对顺序。所以每一轮的局部最优代价可以直接累加，不需要回头调整。这就是贪心策略能成立的根本原因。

3. 完整代码实现与边界处理

3.1 排序与主流程

实现思路很简单：

• 读入所有人的过河时间，排序；
• 用一个变量 n 表示当前还没过河的人数；
• 当 n 大于 3 时，进入循环，每轮把答案加上 min(tA, tB)，然后 n 减 2；
• 循环结束后，根据剩余人数 1、2、3 分别处理。

这里有一个关键点：为什么循环条件是 n > 3，而不是 n > 2？因为当剩余 3 个人时，不能用“送走两个最慢的人”的策略来套。比如 [1, 2, 5]，如果按策略 A 算，tA = 2 * 1 + 5 + 2 = 9，然后剩 1 个人再加 1，总共 10；但实际最优是 8。剩余 3 个人时，最优方案是 a[0] + a[1] + a[2]，比如 1 和 2 先过，1 回来，1 和 5 再过，耗时 2 + 1 + 5 = 8。所以必须单独处理。

3.2 C++ AC代码

下面贴一份完整的 C++ 实现，带注释，可以直接用：

#include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while (T--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); int ans = 0; while (n > 3) { // 策略A：最快者护送两个最慢者 int tA = 2 * a[0] + a[n - 1] + a[n - 2]; // 策略B：最快两人配合接力 int tB = a[0] + 2 * a[1] + a[n - 1]; ans += min(tA, tB); n -= 2; } if (n == 3) { ans += a[0] + a[1] + a[2]; } else if (n == 2) { ans += a[1]; } else { ans += a[0]; } cout << ans << endl; } return 0; }

注意这里n是动态变化的，a[n-1]和a[n-2]始终表示当前剩余未过河的人里最慢的两个。由于数组已经排序，即使 n 变小，前几个元素仍然是剩余的人里最快的几个。

3.3 其他语言要点

如果你用 Java，核心逻辑一样，只是排序用Arrays.sort(a)，读入用Scanner。用 Python 的话，排序用sorted(a)，代码可以写得很短：

t = int(input()) for _ in range(t): n = int(input()) a = sorted(map(int, input().split())) ans = 0 while n > 3: ans += min(2 * a[0] + a[n - 1] + a[n - 2], a[0] + 2 * a[1] + a[n - 1]) n -= 2 if n == 3: ans += a[0] + a[1] + a[2] elif n == 2: ans += a[1] else: ans += a[0] print(ans)

Python 写这类题很舒服，唯一要注意的是多组数据输入时，每组的 n 和数组要读对，别因为换行问题出错。

3.4 边界条件：n=1、2、3

这里把边界情况单独列出来，因为很多人在这里翻车。

• n = 1：只有一个人，他直接划船过去就行，答案是 a[0]；
• n = 2：两个人一起过河，耗时是两人中较慢的那个，也就是 a[1]；
• n = 3：三个人没有简单的一轮送走方案，最优是 a[0] + a[1] + a[2]。可以理解为：a[0] 和 a[1] 先过，a[0] 回来，然后 a[0] 和 a[2] 再过。这个方案也等价于 a[0] 和 a[2] 先过，a[0] 回来，a[0] 和 a[1] 再过，结果一样。

如果你在循环里把 n > 3 写成了 n >= 3，n = 3 时就会进入循环，然后把 3 个人拆成“2 + 1”处理，结果就会偏大。这个细节值得记下来。

4. 样例推演与复杂度分析

4.1 经典样例手算

用经典的 [1, 2, 5, 10] 完整走一遍：

初始数组 [1, 2, 5, 10]，n = 4，进入循环：

• tA = 2 * 1 + 10 + 5 = 17；
• tB = 1 + 2 * 2 + 10 = 15；
• 取较小的 15，ans = 15，n 变为 2。

循环结束，n = 2，ans += a[1] = 2，最终 ans = 17。

再看对应的实际过河方案：1 和 2 先过；1 回来；5 和 10 过；2 回来；1 和 2 过。总耗时 2 + 1 + 10 + 2 + 2 = 17。和代码输出完全一致。

4.2 几组小数据验证

为了加深理解，再手算几组数据：

第二组 [1, 9, 10, 11] 比较有意思：tB = 1 + 2 * 9 + 11 = 30，tA = 2 + 11 + 10 = 23，所以选 A。实际方案：1 带 11 过，1 回，1 带 10 过，1 回，最后 1 和 9 过，总耗时 11 + 1 + 10 + 1 + 9 = 32。如果强行用 B，会变成 9 + 1 + 11 + 9 + 9 = 39，明显更差。这就说明不是所有情况都适合策略 B。

第三组 [1, 2, 3, 4, 5] 验证一下：第一次循环，tA = 2 * 1 + 5 + 4 = 11，tB = 1 + 2 * 2 + 5 = 10，取 10；剩余 [1, 2, 3]，加 6，总 16。手动模拟可以验证这个结果，说明代码逻辑对“每轮取 min”的依赖是稳定的。

4.3 时间复杂度与数据范围

排序是 O(n log n)，贪心循环每一轮 O(1)，总共最多执行 n/2 轮，所以整体复杂度就是 O(n log n)。对于 n 最大 1000 甚至更大的数据量，这个复杂度毫无压力。空间上只需要一个数组，O(n) 的存储。

这道题的核心不在于性能，而在于策略选择，所以时间复杂度和空间复杂度都不是瓶颈，真正要理解的是那两行 min 的决策逻辑。

5. 常见问题与避坑记录

5.1 只套用一种策略导致错误

最常见的错误是只使用策略 A，也就是让最快的人来回接送所有人。这种思路在次慢者和第二快者差距大的时候是对的，但遇到 [1, 2, 5, 10] 这样的数据就会差 2 分钟。反过来，如果只使用策略 B，遇到 [1, 9, 10, 11] 这样的数据也会差很多。所以 min 不是可选项，是必须项。

我见过有人把题目改成“每次选最快的和最慢的一起过”，这其实是另一种错误变体。这种方案会让最慢的人拖累最快的人很多次，结果往往比两种标准策略都差。简单说：最慢的人适合和最慢的人“打包”，而不是永远被最快的人护送。

5.2 排序方向与下标错位

排序方向搞反是另一个常见问题。如果你按降序排列，a[0] 变成最慢的人，那么所有公式全部失效。建议从一开始就按升序排序，让 a[0] 是最快的，a[n-1] 是最慢的，并且记住在循环里动态更新 n，保证 a[n-1] 和 a[n-2] 始终指向当前剩余最慢的两个人。

还有一个小细节：如果你用 vector 存数据，在 n 减到 2 或 3 之后，不要再访问 a[n] 之类的越界位置。有些人复制粘贴代码时 n 和原始数组大小混淆，下标越界报错或者答案错乱，就是这个原因。

5.3 循环边界写错

循环条件必须是 n > 3。写成分号写成 n >= 3 或者 n >= 4 都会出错。n >= 3 会导致剩余 3 人时也按“送走两人”的公式处理，结果偏大；n >= 4 会导致剩余 4 人时提前退出循环，结果也偏小。这里没有商量的余地，就是 n > 3。

5.4 多组测试数据的输入输出问题

POJ 1700 这类题通常是多组数据，第一行是测试组数 T。每组数据内部先读 n，再读 n 个数。有人会在 while 循环里忘记更新 n，或者复用同一个 vector 不清空，导致下一组数据混入上一组的内容。建议每组数据都重新定义一个 vector，或者显式 clear() 一次。输出时每组一行，别把答案累加到上一组。

6. 同源变体与延伸思考

6.1 桥与手电筒的变体

快速渡河问题其实有一个更广为人知的名字叫“桥与手电筒问题”，规则几乎一样：几个人在夜晚过桥，桥上每次最多过两个人，只有一把手电筒，过桥速度由慢者决定。很多算法教材里都用它来讲解贪心策略。

变体玩法有很多：如果每次最多能过 k 个人，策略会变得更复杂，可能需要分组讨论；如果每个人速度都一样，那答案就简单了，只需要计算必要的过河次数乘以单次耗时；如果允许某些人不带灯直接过去，规则就变了，贪心策略也要重新推导。理解了基本型的两种策略之后，遇到这些变体会更容易上手。

6.2 贪心与动态规划的联系

这道题还有一个有意思的地方：它也可以从动态规划的角度去理解。每一轮决策本质上是“处理掉两个最慢的人”，这个过程天然具有无后效性，所以 DP 也能求解。常见的做法是定义状态表示剩余人数，然后用递推方程在策略 A 和策略 B 之间取转移。不过对于这道题，贪心解法更简洁，代码也更短，这也是为什么它被归为贪心经典题。

如果你在学习算法时就遇到过类似题，你会发现这个“min 两种固定策略”的套路，其实在很多贪心题里都有出现。核心思想就是：把问题分解成若干轮，每一轮只有有限的几种最优模式，然后取最小值递推下去。

6.3 一点个人体会

这道题我前前后后写过很多遍，每次写都能发现一点新的理解。最开始我也只想到最快者护送，被样例卡住后才意识到策略 B 的存在；后来又花了很长时间才想明白，为什么取 min 就一定是全局最优。现在回头看，这题的精髓就在那个 min 上：它是一种“不把话说死”的贪心，两种策略并行比较，选更优的走。这也提醒我，遇到看似简单的贪心题，不要急着写循环，先把所有可能的“最优子结构”列出来，再决定每一步怎么走。刷题如此，实际做技术方案也一样。