n 人带一个手电筒过桥的最短总时间
哪些公司问过
答案要点
- 先按过桥时间升序排序,每轮把最慢的两人送过桥,问题规模减二
- 方案一:最快者往返陪送,代价 2a1+a(n-1)+an
- 方案二:最快两人先过,最慢两人同行,代价 a1+2a2+an,两方案取小
- 边界:1 人 a1,2 人 a2,3 人 a1+a2+a3;时间复杂度主要来自排序 O(n log n)
易错点
- 忘记排序,或者只用最快者往返这一种方案
- 边界处理错:3 人时答案是 a1+a2+a3,不是套用两人一组的公式
- 把返回手电筒的时间漏算,只累加了去程时间
面试官常见追问
- 为什么不能固定只用其中一种方案?
- 用动态规划怎么写?
- 如果要输出具体过桥步骤怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。