LeetCode 1029. 两地调度
题目描述
题意分析
有
2n个人，每个人分别有前往城市 A、城市 B 的费用。必须给每人安排一个城市，且两个城市恰好各有n人，求所有安排中的最低总费用。不能让每个人都直接选择自己更便宜的城市，因为人数可能不满足限制；也不能只看某一城市的绝对费用，还要考虑这个人被分配到另一城市的代价。
解法：按差值排序
核心思路
[!blue]
先把“所有人都去 B”作为统一基准，总费用是所有 B 费用之和。最终需要恰好选出
n个人改去 A，某个人的费用变化为A费用 - B费用，记作差值。基准费用对所有方案相同，因此最小化总费用，就等价于从这些差值中选
n个，让它们的和最小。差值越小，改派 A 越划算：负值表示节省，正值表示增加，二者可以直接放在同一个升序比较中。交换论证也能说明这一点。若某方案把较大差值的人选去 A，却让较小差值的人留在 B，交换这两个人的城市不会改变各城人数，但总费用会减少或不变。不断消除这种选择，就会得到差值最小的前
n人去 A 的安排，所以排序选择是最优的。实现中无需真的先加基准再加差值。按差值排好后，直接累加前半的 A 费用与后半的 B 费用，得到的就是同一方案的实际总价。差值相同的人互换不会改变结果。
解题步骤
- 对每个人计算选择 A 相对 B 的费用差，按这个差值升序排序。
- 令
n = costs.length / 2，将前n人安排到 A，后n人安排到 B。- 累加对应城市的实际费用并返回。代码会原地改变输入数组的顺序。
代码实现
class Solution {
public int twoCitySchedCost(int[][] costs) {
// 按改去 A 的额外费用排序，优先选择差值最小的人。
Arrays.sort(costs, (a, b) -> Long.compare((long) a[0] - a[1], (long) b[0] - b[1]));
int n = costs.length / 2;
int answer = 0;
for (int i = 0; i < n; i++) {
// 前半去 A，后半去 B，两个城市恰好各分到一半人数。
answer += costs[i][0] + costs[i + n][1];
}
return answer;
}
}
import "sort"
func twoCitySchedCost(costs [][]int) int {
// 按改去 A 的额外费用排序，优先选择差值最小的人。
sort.Slice(costs, func(i, j int) bool {
left := int64(costs[i][0]) - int64(costs[i][1])
right := int64(costs[j][0]) - int64(costs[j][1])
return left < right
})
n := len(costs) / 2
answer := 0
for i := 0; i < n; i++ {
// 前半去 A，后半去 B，两个城市恰好各分到一半人数。
answer += costs[i][0] + costs[i+n][1]
}
return answer
}
复杂度分析
- 时间复杂度：设总人数为 N，时间为 $O(N\log N)$，排序占主导。
- 空间复杂度：Java 对对象数组排序最坏需要 $O(N)$ 辅助空间；Go 排序的调用栈为 $O(\log N)$，求和只用常数空间。
关键点总结
[!green]
- 固定一侧作基准后，人数限制变成选择固定数量的改派差值。
- 差值表达的是选择之间的代价变化，单边费用无法提供这个信息。
- 交换只调整谁占用 A 的名额，不改变人数，且可以证明差值排序不劣于任何方案。
易错点总结
[!yellow]
- 每个人独立选择较便宜城市，可能让某一城市人数超过
n。- 只按 A 费用排序，忽略了这些人留在 B 的成本，不能保证整体最优。
- 按差值降序却仍让前半去 A，会优先选择改派代价更高的人。
- 排序比较器用多个整数减法拼接比较，容易把差值比较写错；现代码先提升类型再比较两个差值。
- 求和时仍使用排序前的原下标分组，会与差值选择的人员集合不一致。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2611. 老鼠和奶酪 | 中等 | 同样先固定全部选择一侧的基准，再按选择另一侧的收益差挑固定数量；本题最小化费用，原题最大化奖励。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！