限时过桥问题的最优过桥策略
哪些公司问过
答案要点
- 过桥时间按慢者计,由最快的人负责送灯来回
- 让最慢的两人同组过桥,次慢者的时间被最慢者“吸收”
- 五人1、3、6、8、12秒的版本最优29秒,在30秒内;一人逐个陪送需32秒
- 四人1、2、5、8分钟的版本最短15分钟
- 通用解:排序后每轮比较两种送最慢两人的方案取小,剩三人或两人时直接计算
易错点
- 只背步骤,说不清为什么最慢两人要一起过
- 漏算送灯回程的时间
- 人数或时间变了仍生搬硬套固定步骤,应按通用比较法计算
面试官常见追问
- 为什么不能一直让最快的人陪送?
- 两种送法分别在什么情况下更优?
- 人数为n时复杂度是多少?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。