两地调度:一半去北京一半去广州的最低费用
哪些公司问过
答案要点
- 以每人去北京与去广州的费用差作为排序依据
- 按差值升序,前 n/2 人去北京,其余去广州
- 用交换论证证明贪心正确:交换违反顺序的两人不会使总费用增加
- 时间复杂度 O(n log n),主要是排序开销
- 注意 n 为偶数的前提,数值大时用 long 累加
易错点
- 每人直接选更便宜的城市,导致两边人数不平衡
- 只按北京费用排序,忽略了两地的相对差值
- 累加时用 int 导致溢出
面试官常见追问
- 能不能用动态规划做?
- 如果要求 k 人去北京而不是一半呢?
- 能否不做完整排序?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。