面试题库 › 客户端 › n 人带一个手电筒过桥的最短总时间

n 人带一个手电筒过桥的最短总时间

难度 ★★☆在 1 场真实面经中被问到 方向:客户端考点:贪心与回溯

哪些公司问过

字节跳动1

常见岗位:C/C++ 软件开发

答案要点

  1. 先按过桥时间升序排序,每轮把最慢的两人送过桥,问题规模减二
  2. 方案一:最快者往返陪送,代价 2a1+a(n-1)+an
  3. 方案二:最快两人先过,最慢两人同行,代价 a1+2a2+an,两方案取小
  4. 边界:1 人 a1,2 人 a2,3 人 a1+a2+a3;时间复杂度主要来自排序 O(n log n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题