【算法面试题】:小明过桥问题

时间:2022-03-21 09:42:59

题意

现在小明一家过一座桥,过桥时候是黑夜,所以必须有灯。现在小明过桥要1秒,小明的弟弟要3秒,小明的爸爸要6秒,小明的妈妈要8秒,小明的爷爷要12秒。每次此桥最多可过两人,而过桥的速度依过桥最慢者而定,而且灯在点燃后30秒就会熄灭。问小明一家如何过桥?

方法

这个题目最需要解决的就是谁掌灯的问题,肯定需要用过桥时间段的人回来掌灯,因为这样会耗时最少,当然,两个较大的人肯定需要一起过去,不然耗时太大。所以,理想的准备情况是这个样子的- -

小明 + 弟弟 过去 ——3秒
小明 回来—— 1秒
小明 + 爸爸 过去 —— 6秒
小明 回来 —— 1秒
爷爷 + 妈妈 过去 —— 12秒
弟弟 回来 —— 3秒
弟弟 + 小明 过去 —— 3秒

一共 29秒,巧妙的方法吧?