两地调度 图解题解

这道题到底在问什么

costs

[[10,20],[30,200],[400,50],[30,20]]

N

2(各去 2 人)

输出

110

最优解：一步一步想明白

1. 3关键问题:名额有限,该让谁去 A?衡量标准是每个人的 aCost − bCost:这个差越小(越负),说明他去 A 比去 B 划算得越多,就越该占 A 的名额。
2. 4于是策略定型:按 aCost − bCost 升序排序,排在前一半的人去 A(他们去 A 最赚),后一半去 B。下面这排格子放的就是每个人的差值 aCost − bCost。
3. 5差值数组,准备排序格子里是每个人的 aCost − bCost:p0=−10、p1=−170、p2=+350、p3=+10。负得越多越该去 A,正得越多越该去 B。现在把它们从小到大排序。
4. 6指针看 −10,先记它为候选最小排序就像每次挑出还没排好的最小值放到最前。先把位置 0 的 −10 当作候选最小,指针往右一格格比。
5. 7−170 < −10,更新候选最小指针挪到位置 1,−170 < −10,更小!候选最小(绿框)更新成 −170(p1 去 A 比去 B 省 170,最划算)。
6. 8继续扫位置 2、3指针继续扫到位置 2(350)、位置 3(+10),都比 −170 大,候选最小不变。一趟扫完确认 −170 是全场最小。
7. 9−170 ↔ −10把 −170 和位置 0 的 −10 交换。现在位置 0 是 −170,锁定不动(变绿)。
8. 10扫描位置 1~3:−10 最小继续在还没排好的 −10、350、+10 里挑最小。−10 最小,而它正好已经在位置 1,不用换。
9. 11位置 1 排好位置 1 锁定为 −10。已经排好的前两个是 −170、−10,正是最该去 A 的两个人。
10. 12候选最小 = 350前两位已锁定,未排好区从位置 2 开始。先把 350 记为候选最小,继续往右比。
11. 13扫描位置 3:+10 < 350指针到位置 3,+10 < 350,更小!最小是 +10(在位置 3),接下来把它换到位置 2。
12. 14+10 ↔ 350交换后位置 2 是 +10,锁定。最后剩 350 自然落在位置 3。
13. 15全部升序排好排序完成:−170, −10, +10, +350。对应的人依次是 p1、p0、p3、p2。越靠前的人去 A 越划算,接下来前一半去 A、后一半去 B。
14. 16位置 0、1 → A 城N = 总人数 ÷ 2 = 2。排在前 2 位的 p1、p0 去 A(绿色),后 2 位暂时灰着,他们要去 B。
15. 17total = 0 → 30第一个去 A 的是 p1,加上他的 aCost = 30。总费用 total = 30。
16. 18total = 30 → 40第二个去 A 的是 p0,加上他的 aCost = 10。总费用累加到 total = 40。A 城名额满了。
17. 19前一半锁定,A 组 = 30+10A 城两个名额已满,A 组小计 40(30 + 10)。接下来把后一半的人都送去 B。
18. 20位置 2、3 → B 城剩下的 p3、p2 去 B(蓝色)。他们差值为正,本就去 B 更省。开始累加他们的 bCost。
19. 21total = 40 → 60p3 去 B,加上他的 bCost = 20。总费用 total = 60。
20. 22total = 60 → 110最后 p2 去 B,加上 bCost = 50。总费用累加到 total = 110。所有人都分配完了。
21. 23A:{p1,p0}=40 + B:{p3,p2}=70 = 110 ✓答案 110!绿色去 A(40)、蓝色去 B(70)。按差值排序、前一半去 A,就拿到了全局最优。
22. 24为什么排序就一定最优?因为每个人去 A 相对去 B 的「净省」就是 −(aCost−bCost),要让 N 个去 A 的人净省最多,就该挑差值最小的 N 个——这正是排序前一半。
23. 28错误键:按 aCost 升序假如按 aCost 排序:前两小是 p0(10)、p1(30) 去 A=40,p3、p2 去 B=70,这例恰好也得 110;但换一组数据(如有人 aCost 小却 bCost 更小)就会选错——必须用差值才稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def twoCitySchedCost(self, costs):
        costs.sort(key=lambda c: c[0] - c[1])   # 按 aCost-bCost 升序
        n = len(costs) // 2
        total = 0
        for i in range(len(costs)):
            total += costs[i][0] if i < n else costs[i][1]   # 前一半去A,后一半去B
        return total

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b){
            return a[0] - a[1] < b[0] - b[1];
        });
        int n = costs.size() / 2, total = 0;
        for (int i = 0; i < (int)costs.size(); i++) {
            total += (i < n) ? costs[i][0] : costs[i][1];
        }
        return total;
    }
};

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return (a[0] - a[1]) - (b[0] - b[1]);
            }
        });
        int n = costs.length / 2, total = 0;
        for (int i = 0; i < costs.length; i++) {
            total += (i < n) ? costs[i][0] : costs[i][1];
        }
        return total;
    }
}

复杂度

面试官可能追问