潜水最优策略

潜水最优策略

Eviarch Lv2

题目

一支队伍由 n 个人组成.在潜水时必须使用氧气瓶,但是每支队伍只有一个氧气瓶.最多两个人同时使用一个氧气瓶,但此时两人必须同步游泳,因此到达河对岸的时间等于较慢的一个单独游到终点所需要的时间.好在大家都很友好,因此任何两个人都愿意一起游泳.安排一种潜水策略,使得最后一名选手尽早到达终点。

Input

先输入一个整数 n,表示队伍中人数,再依次输入每个人游到对岸所需时间(乱序)

Output

输出队伍到达河对岸最少的时间

Sample Input Sample Output
3 1 3 4 8
6 1 2 5 6 8 9 27
4 1 10 11 12 35
Warn

第三组数据是后来补的反例。原来那份只按固定套路循环的代码在这组数据上会输出 43,而正确答案是 35。原因见下文。


建模:这就是经典的「过桥问题」

把氧气瓶换成火把,这道题就是大名鼎鼎的 Bridge and torch problem:一座桥最多容纳 2 人,过桥必须有火把,火把只有 1 支,求全员过桥的最短时间。

先做几个观察,它们决定了后面所有推理。设排序后的用时为

a0≤a1≤…≤an−1a_0 \le a_1 \le \dots \le a_{n-1}

观察 1:返回时永远只有 1 个人。 两个人一起返回,耗时取较慢者,等于把其中一人白白送回起点,之后他还要再过一次河。拆开走不会更差。

观察 2:过河次数至少是 2n−32n-3。 设前进 ff 次、返回 bb 次。氧气瓶必须跟着人走,所以瓶子两侧交替,b=f−1b = f - 1。每次前进至多带 2 人,每次返回至少带 1 人,于是净过河人数 ≤2f−b=f+1\le 2f - b = f + 1;要送 nn 个人过去就需要 f≥n−1f \ge n - 1,于是总次数

f+b=2f−1≥2n−3f + b = 2f - 1 \ge 2n - 3

要同时取到等号(f=n−1f = n-1),必须每一次前进都恰好满载 2 人、每一次返回都只带 1 人——这正是下面 A、B 两种送法的形状。2n−32n-3 是次数下界:返回多带人会被观察 1 排除,前进不满载会多出空趟,也能换成满载而不增加耗时。A、B 每轮正好满足这个等号条件,所以最优解取得到这个次数,而不只是次数被事先固定死。

观察 3:可以每次消掉最慢的两个人。 最慢的两人记为 x=an−2x = a_{n-2}、y=an−1y = a_{n-1}。他们迟早要过河,而把他们送过去、并把氧气瓶送回起点,只有两种值得考虑的送法(由下文引理 1 证明)。送走这两人之后,剩下的人构成一个规模减 2 的同构子问题。


贪心策略:每一轮 A / B 二选一

方案 A —— 由最快的人来回护送

步骤 动作 耗时
1 a0a_0 和 yy 过河 yy
2 a0a_0 带瓶返回 a0a_0
3 a0a_0 和 xx 过河 xx
4 a0a_0 带瓶返回 a0a_0

A=2a0+x+yA = 2a_0 + x + y

两个慢的人没有配对,xx 和 yy 各付一次全程。好处是回来送瓶的一直是最快的 a0a_0。

方案 B —— 最快的两人先过去接应

步骤 动作 耗时
1 a0a_0 和 a1a_1 过河 a1a_1
2 a0a_0 带瓶返回 a0a_0
3 xx 和 yy 过河 yy
4 a1a_1 带瓶返回 a1a_1

B=a0+2a1+yB = a_0 + 2a_1 + y

关键在第 3 步:最慢的两人一起过河,只按 yy 计时,xx 等于白送。代价是多花一次 a1a_1 送瓶子回来。

什么时候选哪个

A−B=(2a0+x+y)−(a0+2a1+y)=a0+x−2a1A - B = (2a_0 + x + y) - (a_0 + 2a_1 + y) = a_0 + x - 2a_1

所以

  • x>2a1−a0x > 2a_1 - a_0:第二慢的人足够慢,选 B(把 xx 藏进 yy 那一趟更划算);
  • x≤2a1−a0x \le 2a_1 - a_0:选 A(a1a_1 来回的成本已经不低于把 xx 单独送过去)。

一句话记忆:从 B 改走 A,要单独付 xx,省下 2a1−a02a_1 - a_0;省得多就选 A,省不下就选 B。

为什么每轮取小就是全局最优

  • 引理 1(局部穷举):在”送走 x,yx, y 且把瓶子送回起点”这一段里,最优安排只可能是 A 或 B。由观察 2 的等号条件,这段里的前进趟必须满载 2 人、返回趟只带 1 人;这样 x,yx, y 所乘的趟要么不同行、要么同行,同行时同伴、接应与送瓶者都只可能是 a0a_0 或 a1a_1(同伴更慢只会更亏)。于是只剩两种骨架:同行 → 必须先把 a1a_1 送过去接应、事后再返回送瓶,即 B;不同行 → a0a_0 各陪一趟并各自返回,即 A。严格证明写成标准交换论证即可,这里还有暴力对拍结果作旁证。
  • 引理 2(无后效性):A、B 两种送法结束时,起点侧剩下的都是同一批人(少了 x,yx, y),瓶子也在起点。子问题与原问题形式完全一致,只与剩下的人有关。
  • 归纳:n≤3n \le 3 时直接枚举可验证;n≥4n \ge 4 时,最优解 = 本轮最优(引理 1)+ 剩余 n−2n-2 人的最优(归纳假设)。

收尾的三种基本情况(不需要再送瓶回来):

剩余人数 走法 耗时
1 a0a_0 自己过去 a0a_0
2 a0,a1a_0, a_1 一起过去 a1a_1
3 a0,a1a_0,a_1 过 → a0a_0 回 → a0,a2a_0,a_2 过 a0+a1+a2a_0 + a_1 + a_2

原写法的问题

原来那份代码的思路是:固定 2n−32n-3 次过河,按 第二快 → 最快 → 最慢 → 第二快 四个一组循环累加。

这个套路恰好等价于”每一轮都只走方案 B”:arr[1] + arr[0] + arr[最慢] + arr[1] 正是 B=a0+2a1+yB = a_0 + 2a_1 + y。它默认了”B 永远不比 A 差”,而这不成立。

反例 1 10 11 12(a0=1,a1=10,x=11,y=12a_0=1,\ a_1=10,\ x=11,\ y=12):

轮次 x, y 方案 A 方案 B 应选
1 11, 12 2⋅1+11+12=252\cdot1+11+12 = 25 1+2⋅10+12=331+2\cdot10+12 = 33 A
收尾 1, 10 — — 10

最优 =25+10=35= 25 + 10 = 35,而只走 B 得 33+10=4333 + 10 = 43,多花 8。

info

样例 1 2 5 6 8 9 恰好每一轮都是 B 更优(第 1 轮 A=19/B=14,第 2 轮 A=13/B=11),所以原代码能过样例。样例通过不等于策略正确,这是这次踩坑最值得记的一点。


代码实现

Python(每轮 A/B 取小,附暴力校验)

这段程序会多打印每一轮的 A/B 选择,方便和后文的对照表核对。按原题提交时,只输出总时间那一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import heapq
import sys
from itertools import combinations


def optimal_dive(times, strategy="auto"):
"""返回 (最少总用时, 每轮决策列表)。

strategy: "auto" 每轮取 A/B 较小者(最优)
"a" / "b" 强制只用某一种(用于对比、复现原写法)
"""
n = len(times)
if n == 0:
return 0, []

a = sorted(times)
total, decisions = 0, []
m = n # 尚未过河的是 a[0..m-1]

while m > 3:
a0, a1, x, y = a[0], a[1], a[m - 2], a[m - 1]
cost_a = 2 * a0 + x + y
cost_b = a0 + 2 * a1 + y
use_a = (cost_a <= cost_b) if strategy == "auto" else (strategy == "a")
total += cost_a if use_a else cost_b
decisions.append({"x": x, "y": y, "A": cost_a, "B": cost_b,
"chosen": "A" if use_a else "B"})
m -= 2 # 最慢的两人已过河

if m == 1:
total += a[0]
elif m == 2:
total += a[1]
elif m == 3:
total += a[0] + a[1] + a[2]
return total, decisions


def brute_force(times):
"""状态压缩 Dijkstra:状态 = (对岸的人集合, 瓶子在哪一岸)。"""
n = len(times)
if n == 0:
return 0
full = (1 << n) - 1
dist = {(0, 0): 0}
pq = [(0, 0, 0)] # (累计耗时, mask, 瓶子侧 0=起点 1=对岸)

while pq:
d, mask, side = heapq.heappop(pq)
if d != dist.get((mask, side)):
continue
if mask == full and side == 1:
return d

if side == 0: # 瓶子在起点:送 1 或 2 个人过去
avail = [i for i in range(n) if not (mask >> i) & 1]
for k in (1, 2):
for group in combinations(avail, k):
cost = max(times[i] for i in group)
nmask = mask
for i in group:
nmask |= 1 << i
if d + cost < dist.get((nmask, 1), 1 << 60):
dist[(nmask, 1)] = d + cost
heapq.heappush(pq, (d + cost, nmask, 1))
else: # 瓶子在对岸:只派 1 个人回来(已采用观察 1,不枚举两人同返)
for i in range(n):
if (mask >> i) & 1:
nmask = mask & ~(1 << i)
if d + times[i] < dist.get((nmask, 0), 1 << 60):
dist[(nmask, 0)] = d + times[i]
heapq.heappush(pq, (d + times[i], nmask, 0))


if __name__ == "__main__":
nums = [int(x) for x in sys.stdin.read().split()]
n, times = nums[0], nums[1:1 + nums[0]]
total, decisions = optimal_dive(times)
print(total)
for d in decisions:
print(f" x={d['x']:>3} y={d['y']:>3} A={d['A']:>4} B={d['B']:>4} -> {d['chosen']}")

C++(修正版,保持原来的 O(n) 写法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
if (!(cin >> n)) return 0;

vector<long long> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end());

long long ans = 0;
int r = n - 1; // 尚未过河的是 a[0..r]

while (r + 1 > 3) { // 每轮送走最慢的两人
long long A = 2 * a[0] + a[r - 1] + a[r]; // 最快的人来回护送
long long B = a[0] + 2 * a[1] + a[r]; // 最快两人先接应
ans += min(A, B);
r -= 2;
}

if (r + 1 == 1) ans += a[0]; // 1 人
else if (r + 1 == 2) ans += a[1]; // 2 人
else if (r + 1 == 3) ans += a[0] + a[1] + a[2]; // 3 人

cout << ans;
return 0;
}

改动只有三处:

  1. 不再用 i % 4 的固定套路,而是每轮显式比较 A 和 B;
  2. 用 r 表示”还没过河的人”,比 control 计数器更直观,也不容易在奇偶人数上出错;
  3. 用 long long,避免用时较大时溢出(原代码 int arr[100] 也顺手解决了人数上限问题)。

原来那份代码里 n == 1 的特判可以省掉:上面的收尾分支已经覆盖了 1 / 2 / 3 人。


验证

输入 每轮决策 贪心结果 只走 A 只走 B(原写法) 暴力校验
1 3 4 收尾 8 8 8 8 ✓
1 2 5 6 8 9 B(14), B(11) 27 34 27 27 ✓
1 2 5 10 B(15) 17 19 17 17 ✓
1 10 11 12 A(25) 35 35 43 35 ✓
1 2 5 10 15 B(20) 28 35 28 28 ✓

另外用随机数据做了对拍:300 组、n≤9n \le 9、用时 1~60。在只允许 1 人返回的前提下,贪心结果与状态压缩 Dijkstra 完全一致。


复杂度

方法 时间 空间 说明
贪心 O(nlog⁡n)O(n\log n) O(n)O(n) 排序主导,决策循环 O(n)O(n)
暴力(状态压缩 Dijkstra) O(2n⋅n2)O(2^n \cdot n^2) O(2n)O(2^n) 只用于校验(状态 == 对岸集合 ++ 瓶子的岸),n≤12n \le 12 可跑

小结

  • 本题 = 过桥问题,过河次数下界 2n−32n-3,且最优解每次前进必须满载 2 人。
  • 每轮只需比较两种送法:A=2a0+x+yA = 2a_0 + x + y、B=a0+2a1+yB = a_0 + 2a_1 + y,取小者,规模减 2。
  • 判据 A−B=a0+x−2a1A - B = a_0 + x - 2a_1:第二慢的人够慢就选 B,第二快的人来回太贵就选 A。
  • 固定套路(只走 B)在 x≤2a1−a0x \le 2a_1 - a_0 的数据上会错,反例 1 10 11 12 差 8。
  • 拿不准最优性时,写一个 O(2n)O(2^n) 的暴力对拍,比反复”浅浅验证”可靠得多。
  • Title: 潜水最优策略
  • Author: Eviarch
  • Created at : 2025-06-10 15:04:34
  • Updated at : 2026-10-22 15:53:00
  • Link: https://blog.eviarch.com/2025/06/10/潜水最优策略/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments