过桥问题

Bridge Crossing

专题: Brainteaser / 脑筋急转弯
难度: L2
来源: QuantQuestion

题目详情

David、Emma、Frank、Grace 需要在夜里过桥。桥上一次最多容纳 2 人，且必须携带唯一的一盏灯才能过桥。两人同行的用时等于其中较慢者。

他们过桥时间分别为：David 10 分钟，Emma 5 分钟，Frank 2 分钟，Grace 1 分钟。

问：全员到达对岸所需的最短时间是多少？

David, Emma, Frank, and Grace need to cross a river. The only possible way to cross the river is a bridge that can only hold at maximum $2$ people at once. It's night time, so they can only cross the bridge using a lantern and they only have $1$ lantern. Each pair of people can only cross at the pace of the slowest person. All people need to get across as fast as possible. Their crossing times are as follows: David takes $10$ minutes, Emma takes $5$ minutes, Frank takes $2$ minutes, and Grace takes $1$ minute. What is the minimum time required for all of them to get across to the other side?

解析

最优思路是让最快的人负责多次带灯返回，同时让最慢的两人同去但不在第一趟。

一种最优方案：

Frank + Grace 过桥：2 分钟。
Grace 带灯返回：1 分钟。
David + Emma 过桥：10 分钟。
Frank 带灯返回：2 分钟。
Frank + Grace 再次过桥：2 分钟。

总时间： $2+1+10+2+2=17$ 分钟。

Original Explanation

The key point is to realize that the person returning with the lantern does not have to be from the most recent pairing. Another point to realize is that David and Emma should go together, since they're the slowest, but not in the first crossing; otherwise, one of them has to go back, which will take too long. Hence, Frank and Grace should go across first, which takes $2$ minutes. Grace is then sent back with the lantern, which takes $1$ minute. David and Emma go across, which takes $10$ minutes. Frank returns with the lantern, which takes $2$ minutes. Finally, Frank and Grace cross again, which takes $2$ minutes, for a total of $17$ minutes.