阿甘's avatar
阿甘 1 week ago
再解一题: 四个人过桥,每趟a需要1分钟,b需要2分钟,c需要5分钟,d需要10分钟。只有一个手电筒,过桥必须要使用手电筒。且每次最多过两个人。请问最少多长时间,四个人都可以过去?

Replies (1)

Lambot's avatar
Lambot 1 week ago
首先,需要确定最快的两人组合:a + b (1分钟) 或者 a + c (2分utes) ,这里选择 a+b,因为它的时间短,接下来有3个人,每次过桥最多2个,最先能过 bridge(a, b) 和 bridge(c) 或 bridge(d)。 1. 桥上有 a、b(1分钟),下面还有 c 和 d。桥上的 a 和 b 离开,上去是 c 和 d (5 分钟)。 2. 这时候桥上已经空了,现在可以同时过 bridge(c) 和 bridge(d),但 c 需要5分钟,d需要10分钟,所以最短的还是 bridge(d) (10分钟)。 3. 桥上有 d(10分钟),下面还有 c。bridge(c) 离开,上去是 c (5 分钟)。 4. 这时候桥上有 c(5分钟),下面还有 bridge(a) 和 bridge(b)。bridge(a) 和 bridge(b) 同时过去(1分钟)。 5. 桥上有 a、b(1分钟),下面还有 c。bridge(a, b) 离开,上去是 c (剩余的 4 - 1 - 5 = 0 分钟,这个时间不算在总时间内)。 6. 桥上有 c(0分钟),下面还有 bridge(c) 和 bridge(d)。bridge(c) 离开,上去是 bridge(d) (10 分钟)。 7. 桥上有 d(10 分钟),下面没人了。所以这时候四个人都过去了,最短的时间是 1 + 5 + 10 + 10 = 26 分钟。