知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 11 - 过桥 / 过河问题 ## 题目 4 个人要在夜间过一座独木桥,一次最多过 2 人。他们只有 1 个手电筒,过桥的人必须有人拿手电筒(意味着每次过桥后,必须有人把手电筒送回对岸)。4 个人的过桥时间分别为 **1 分钟、2 分钟、5 分钟、10 分钟**(两人一起过桥时,按慢的那个人算时间)。 问:所有人都过桥的**最短总时间**是多少? ## 大白话理解 深夜,一座破桥,一次最多走两人,只有一个手电筒。手电筒必须有人来回送。时间按两人中慢的那个算。 ``` 人物: A = 1 分钟(最快) B = 2 分钟 C = 5 分钟 D = 10 分钟(最慢) 起点侧 ────── 桥 ──────→ 终点侧 (所有人) (目标) ``` --- ### 常见错误思路 ``` 直觉:"让最快的人来回跑送手电筒" 方案 A(A 当快递员): A+B 过去 → 2 分钟 A 回来 → 1 分钟 A+C 过去 → 5 分钟 A 回来 → 1 分钟 A+D 过去 → 10 分钟 总时间 = 2 + 1 + 5 + 1 + 10 = 19 分钟 ``` ``` 能更优吗?考虑"最慢的两人一起过"策略: 方案 B(C 和 D 一起过): A+B 过去 → 2 分钟 A 回来 → 1 分钟 C+D 过去 → 10 分钟(两人中最慢的 10 分钟) B 回来 → 2 分钟 A+B 过去 → 2 分钟 总时间 = 2 + 1 + 10 + 2 + 2 = 17 分钟 ✓ 更优! ``` --- ### 策略对比 ``` 策略 1:"最快者来回送" ┌──────────────────────────────────────────────────┐ │ 最快者 A 陪每个人过一次,每次都回来 │ │ │ │ 时间 = 最慢者 + 次慢者 + ... + (n-2) × 最快者 │ │ │ │ 本例:10 + 5 + 1 + 1 = 19 分钟 │ └──────────────────────────────────────────────────┘ 策略 2:"两个最慢的一起过" ┌──────────────────────────────────────────────────┐ │ 最快的两个先过去建立基地,最快的回来, │ │ 最慢的两个一起过去(只用按慢者一次时间), │ │ 次快者回来送手电筒 │ │ │ │ 时间 = T1 + T2 + T_max + T2 + T1 │ │ = 2T2 + T1 + T_max │ │ │ │ 对最慢两人组:T1 + 2T2 + T_max │ └──────────────────────────────────────────────────┘ ``` ``` 通用贪心:每次送最慢的两人过桥,比较两种策略的代价 设当前最慢两人为 X(次慢)和 Y(最慢), 最快两人为 A(最快)和 B(次快) 策略 1 送 X+Y 的代价:A+Y + A+X = 2A + X + Y (A陪Y过→A回→A陪X过→A回,但最后一步A可以留对面) 策略 2 送 X+Y 的代价:A+B + A+Y + B = 2B + A + Y (A+B过→A回→X+Y过→B回→A+B过,把X+Y打包送走) 选择代价小的:min(2A + X + Y, 2B + A + Y) = A + Y + min(2A + X, 2B) ← 简化 实际比较:2A + X vs 2B 如果 2A + X > 2B → 用策略 2 如果 2A + X ≤ 2B → 用策略 1 ``` ``` 手动模拟最优方案(17 分钟): 时间 0 起点: [A(1), B(2), C(5), D(10)] 对岸: [] 手电筒在起点 时间 2 A + B 过桥(按 B 的 2 分钟) 起点: [C(5), D(10)] 对岸: [A(1), B(2)] A 拿手电筒回来(按 A 的 1 分钟) 时间 3 起点: [A(1), C(5), D(10)] 对岸: [B(2)] B 把手电筒给了 A 时间 13 C + D 过桥(按 D 的 10 分钟) 起点: [A(1)] 对岸: [B(2), C(5), D(10)] B 拿手电筒回来(按 B 的 2 分钟) 时间 15 起点: [A(1), B(2)] 对岸: [C(5), D(10)] 时间 17 A + B 过桥(按 B 的 2 分钟) 起点: [] 对岸: [A, B, C, D] 总时间 = 17 分钟 ✓ ``` --- ### 通用解法(N 人过桥) ``` 算法流程(时间排序后 t[1] ≤ t[2] ≤ ... ≤ t[n]): while n > 3: 策略 1 代价 = t[1] + 2*t[2] + t[n] 策略 2 代价 = 2*t[1] + t[n-1] + t[n] 总时间 += min(策略1代价, 策略2代价) n -= 2 (送走最慢两人) // 剩余 1~3 人直接处理 if n == 3: 总时间 += t[1] + t[2] + t[3] // 最快的陪另外两个过 if n == 2: 总时间 += t[2] // 两人一起过 if n == 1: 总时间 += t[1] // 一个人过 ``` ```java public int minBridgeTime(int[] times) { Arrays.sort(times); // 从小到大排序 int n = times.length; int total = 0; // 每次送最慢的两人过桥 while (n > 3) { // 策略 1:最快者来回送 → 2*times[0] + times[n-2] + times[n-1] // 但更准确的单次代价:times[0] + times[n-1] + times[0] = 2*times[0] + times[n-1] // 但 X+Y 一起过的情况, // 实际送走两人:比较两种 int cost1 = times[0] + 2 * times[1] + times[n - 1]; // 策略2 int cost2 = 2 * times[0] + times[n - 2] + times[n - 1]; // 策略1 total += Math.min(cost1, cost2); n -= 2; } // 处理剩余 if (n == 3) { total += times[0] + times[1] + times[2]; } else if (n == 2) { total += times[1]; } else if (n == 1) { total += times[0]; } return total; } ``` --- ## 一句话总结 过桥问题的关键在于比较两种策略:策略 1 是"最快者来回送"(2A+X+Y),策略 2 是"最慢两人打包过"(A+2B+Y)。每次送走最慢的两人时选代价更小的策略,贪心得到全局最优。 --- 下一篇:[12 - 拿石头游戏(巴什博弈)](./12-bash-game.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入