一、什么是“四人过河”经典问题
最早版本见于 MBA/奥数/信息学趣题：
N 个人（通常 N=4）要从左岸到右岸，只有一条小船，容量至多 2 人；
- 船划行时间 = 船上所有人中最大的那一项；
- 船不能空驶，每次必须有人把船划回来；
- 问：让所有人到达对岸的最短总时间是多少？
二、通用数据设定
给出数组 t[1..n]（升序排列），t[i] 表示第 i 个人单独划船所需时间。
例：1、2、5、10（经典 MBA 版）或 1、2、4、8（本题版）。
三、核心观察
- 每次往返至少“送过去 1 人、带回 1 人”，净增 1 人。
- 要把最慢的两个“大数”送过去，通常有两种宏观策略：
S1 “快艇快递”——用最小的 1 号当船夫，来回接人；
S2 “双慢合并”——让两个最慢的一起过河，避免他们分别拖时间。
四、两种基础子 routine
设 t1 ≤ t2 ≤ … ≤ tn
| 策略 | 操作 | 耗时 | 说明 |
|---|---|---|---|
| A | t1,t2 → t1 ← t1,t3 → t1 ← … |
2·t1 + t2 + t3 + … | 1 号来回接 |
| B | t1,tn → t1 ← t1,tn-1 → t1 ← |
2·t1 + tn + tn-1 | 把最慢两个分批送 |
| C | t1,t2 → t1 ← tn-1,tn → t2 ← t1,t2 → |
t2 + t1 + tn + t2 + t2 = 2·t2 + t1 + tn | 双慢合并经典四步 |
策略 C 往往比 策略 B 更省——用“次小”代替“最小”把船带回来，减少大数出现次数。
五、通用贪心算法（适用于任意 n ≥ 3）
- 排序
t[1..n]升序。 - 剩余未过河人数 ≥ 4 时，反复比较：
cost1 = 2·t1 + t_{k-1} + t_k （策略 B）
cost2 = 2·t2 + t1 + t_k （策略 C）
选较小者累加，并把k ← k-2（最慢两人已处理）。 - 剩余 3 人时，固定用 t1+t2+t3（一步送回）。
- 剩余 2 人时，一次
t1,t2 →结束。
时间复杂度：O(n log n)（排序主导）。
六、对本题 1、2、4、8 套用
排序后 [1,2,4,8]
- k=4：cost1=2·1+4+8=14，cost2=2·2+1+8=13 → 选 13，累加 13，剩 [1,2]
- k=2：直接 2 → 累加 2
总最短 = 13 + 2 = 15（与前面手算一致）。
七、记忆口诀
“双慢合并优于单慢分批，只剩三人用一锅端。”
掌握以上模板，无论人数、时间数组怎样变化，都可 30 秒内写出最优方案。