LeetCode 1029. 两地调度

2022-10-12 HGNULB 约 5 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1029. 两地调度

题意分析

有 2n 个人，costs[i] = [aCost, bCost] 表示第 i 个人飞 A 市和飞 B 市各要花多少钱。要求恰好 n 个人去 A、n 个人去 B，求最小总费用。

关键约束是「两边人数必须严格相等」。如果没有这条，每个人各自选便宜的一边即可，题目就不成立了。正是这个名额限制把「独立的 2n 个选择」耦合成了一个整体决策：让某人去 A，就意味着挤掉了另一个人去 A 的名额。

由此引出正确的度量方式。直接比较 aCost 和 bCost 的绝对大小没有意义——真正要比的是「这个人改去 A 而不是 B，会额外多花（或少花）多少钱」，也就是差值 aCost - bCost。差值越小（越负），把 A 的名额给他越划算。这一步把二维的 [aCost, bCost] 降成了一维的可排序键，是全题的转折点。

约束是 costs.length == 2n、1 ≤ n ≤ 100、费用不超过 1000，规模极小，$O(n \log n)$ 的排序绰绰有余；总费用最大约 200 × 1000 = 2 × 10^5，int 完全够用。

边界：n 可以是 1（两个人，一人一边）；两个人的差值可能相等，此时谁去哪边都不影响总额，排序是否稳定无所谓。

解法：按差值排序

核心思路

先假设所有人都去 B，总费用为 sumB。把第 i 个人改派到 A，会让总费用变化：

diff[i] = costs[i][0] - costs[i][1]

现在必须从 2n 个人中恰好改派 n 人，目标变成让选中的 n 个差值之和最小。因此按 diff 升序排序，前 n 人去 A，其余人去 B 即可。差值为负表示改派到 A 还能省钱，差值越小，A 的名额越应该优先给他。

交换论证：若一个方案让差值较大的 j 去 A、差值较小的 i 去 B，且 diff[i] <= diff[j]，交换两人的城市后人数不变，总费用变化为 diff[i] - diff[j] <= 0。不断消除这样的逆序对，最终就得到「排序后前半去 A、后半去 B」的方案，且费用不会增加，因此该方案最优。

代码直接按排序后的位置累加实际费用，不必显式计算 sumB。排序会改变 costs 的顺序，这是本解法唯一的输入副作用。

解题步骤

对每个人计算排序键 A 费用 - B 费用，按该键升序原地排序。

令 n = costs.length / 2。

排序后的前 n 人累加 A 费用，后 n 人累加 B 费用。

样例 [[10,20],[30,200],[400,50],[30,20]] 的差值为 [-10,-170,350,10]。排序后前两人去 A 花 30 + 10，后两人去 B 花 20 + 50，总费用为 110。

反例 [[5,10],[6,1],[7,20],[8,2]] 说明不能按 A 费用排序：按差值选人得到 7 + 5 + 1 + 2 = 15；按 A 费用选前两人去 A 会得到 5 + 6 + 20 + 2 = 33。

代码实现

import java.util.Arrays;

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        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++) {
            answer += costs[i][0] + costs[i + n][1];
        }
        return answer;
    }
}

import "sort"

func twoCitySchedCost(costs [][]int) int {
	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++ {
		answer += costs[i][0] + costs[i+n][1]
	}
	return answer
}

复杂度分析

设总人数为 $N$。

时间复杂度：$O(N \log N)$，排序占主导；求和为 $O(N)$。

空间复杂度：算法自身只用 $O(1)$ 标量，但还需计入标准库排序开销。Java 对对象数组排序最坏需要 $O(N)$ 辅助空间；Go 的 sort.Slice 额外栈空间为 $O(\log N)$。

关键点总结

固定名额的二选一问题，应比较两个选择的相对代价，而不是任一边的绝对费用。

「全部去 B，再改派 n 人」把问题化为选择最小的 n 个增量。

交换论证同时保证人数约束不变，并证明所有逆序安排都不优于差值顺序。

相同差值的人如何排序不影响答案；实现无需依赖稳定排序。

易错点总结

按 A 费用或 B 费用排序：绝对费用没有表达「改派」的机会成本，上面的反例会得到 33 而非 15。

把差值按降序排却仍让前半去 A：样例会得到 650，而正确答案是 110。

每个人独立选择较便宜的城市：[[1,100],[2,100],[3,100],[4,100]] 会把 4 人都送往 A，违反各 n 人的约束。

排序后仍对每个人取 min(A,B)：[[1,2],[1,2],[1,2],[1,2]] 会得到非法答案 4，合法最优值是 6。

Go 排序比较函数必须使用严格的 <；相等时也返回 true 会破坏比较器要求。

比较器里直接做 32 位减法在本题约束下不会溢出，但模板迁移到更大费用范围时会出错；代码先提升到 64 位再求差，避免比较器因溢出破坏顺序。

相似题目

题目	难度	考察点
1005. K 次取反后最大化的数组和	简单	同为排序后取前缀的贪心，但排序键是原值、且要额外处理剩余次数的奇偶性
455. 分发饼干	简单	两个数组各自排序后双指针匹配，贪心对象是「配对」而非「二选一」
881. 救生艇	中等	排序后头尾双指针，每步要同时看最轻与最重两端，约束是每船至多两人
502. IPO	困难	名额固定为 `k` 次，但候选集合随资本增长而动态解锁，需要排序配合大顶堆
630. 课程表 III	困难	按截止时间排序后反悔式贪心，选进来的元素还能被更优的替换掉
1235. 规划兼职工作	困难	排序只是预处理，真正的最优化必须靠 DP 加二分，用来对照「何时排序就够、何时不够」
1353. 最多可以参加的会议数目	中等	同样是名额受限的分配，但每个时间点只有一个名额，需要用小顶堆按截止时间贪心