题目描述
思路解析
一句话答案：LeetCode 1029 两地调度：2N 人要各去 A、B 城一半，按每人 aCost − bCost 的差价升序排，前一半去 A、后一半去 B 累加——差价最小的人去 A 最省，时间 O(n log n)。
各去一半的名额下，总机票钱怎么压到最低
有 2N 个人，第 i 个人去 A 城花 costs[i][0]、去 B 城花 costs[i][1]，要求恰好 N 人去 A、N 人去 B，总机票钱最少。题面例子 costs = [[10,20],[30,200],[400,50],[30,20]]，N = 2，答案 110。卡人的是『各去一半』：没这限制每人挑便宜的城就行，可两边各锁死 N 个名额，就不能各自为政。
每人各挑便宜的城，为什么可能凑不齐名额
最直白是每人挑更便宜的城：这例 p0、p1 去 A、p2、p3 去 B 凑巧各两人；但把 p3 去 B 的价改成 40，四人都想去 A，A 挤三个、B 剩一个，名额崩了，还得挑人赶去 B，绕回『挑谁』。硬枚举也不行：2N 选 N 的组合数 C(2N, N) 随人数爆炸，算不动。
按差价 aCost − bCost 排个序，凭什么就是最优
先定个基准：假设所有人都去 B。要把 N 个人改派去 A，某人从 B 挪到 A，总费用的变化正好是 aCost − bCost 这个差价——为负更省、为正更贵。要凑够 N 个去 A 又让总费用涨最少，就挑差价最负的 N 个人：按 aCost − bCost 升序排，前一半天生就是，取他们 aCost、其余取 bCost，即全局最省。这一步是贪心：拿 aCost − bCost 当尺子把人从省到贵排队，差价越负的越先领 A 的名额，队列排定就照单派完、不再翻盘。
排序 + 前一半取 aCost、后一半取 bCost
代码就三步。第一步，把 costs 按 aCost − bCost 升序排，排序键 c[0] − c[1]。第二步，n = 总人数 ÷ 2 即 A 城名额。第三步，从头遍历，下标在前一半的去 A、累加 costs[i][0]，后一半的去 B、累加 costs[i][1]，遍历完 total 即答案。
四个人的例子，两组小计怎么凑成 110
每人的差价 aCost − bCost：p0 是 10 − 20 = −10，p1 是 30 − 200 = −170，p2 是 400 − 50 = +350，p3 是 30 − 20 = +10。升序排好是 −170、−10、+10、+350，对应 p1、p0、p3、p2。n = 4 ÷ 2 = 2，前两位 p1、p0 去 A：加 p1 的 aCost 30、加 p0 的 aCost 10，A 组小计 40。后两位 p3、p2 去 B：加 p3 的 bCost 20、加 p2 的 bCost 50，B 组小计 70。两组一并，40 + 70 = 110。
排序键写成单城价、名额没卡住，都会翻船
最容易栽的是排序键写成单城价：只按 aCost 或 bCost 排，只盯一座城的贵贱，衡量不出『去 A 比去 B 划算多少』——这例按 aCost 排恰好也得 110，换组数据就会把不该去 A 的人排到前头。名额也松不得：放任每人挑便宜城，A 城可能挤进超过 N 个人，排完序还得硬卡前一半去 A、后一半去 B。
排序 O(n log n)、累加 O(n)，合起来 O(n log n)；原地排序加几个变量，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键问题:名额有限,该让谁去 A?衡量标准是每个人的 aCost − bCost:这个差越小(越负),说明他去 A 比去 B 划算得越多,就越该占 A 的名额。
于是策略定型:按 aCost − bCost 升序排序,排在前一半的人去 A(他们去 A 最赚),后一半去 B。下面这排格子放的就是每个人的差值 aCost − bCost。
起步 · 算出每个人的差值 aCost − bCost：格子里是每个人的 aCost − bCost:p0=−10、p1=−170、p2=+350、p3=+10。负得越多越该去 A,正得越多越该去 B。现在把它们从小到大排序。
排序 · 从位置 0 开始扫：排序就像每次挑出还没排好的最小值放到最前。先把位置 0 的 −10 当作候选最小,指针往右一格格比。
排序 · 比到 −170,更小!：指针挪到位置 1,−170 < −10,更小!候选最小(绿框)更新成 −170(p1 去 A 比去 B 省 170,最划算)。
排序 · 比 350、+10,都更大：指针继续扫到位置 2(350)、位置 3(+10),都比 −170 大,候选最小不变。一趟扫完确认 −170 是全场最小。
交换 · −170 换到位置 0：把 −170 和位置 0 的 −10 交换。现在位置 0 是 −170,锁定不动(变绿)。
排序 · 在剩下里找最小 −10：继续在还没排好的 −10、350、+10 里挑最小。−10 最小,而它正好已经在位置 1,不用换。
锁定 · 位置 1 = −10：位置 1 锁定为 −10。已经排好的前两个是 −170、−10,正是最该去 A 的两个人。
排序 · 先看位置 2 的 350：前两位已锁定,未排好区从位置 2 开始。先把 350 记为候选最小,继续往右比。
排序 · 在剩下里找最小 +10：指针到位置 3,+10 < 350,更小!最小是 +10(在位置 3),接下来把它换到位置 2。
交换 · +10 换到位置 2：交换后位置 2 是 +10,锁定。最后剩 350 自然落在位置 3。
排序完成 · [−170, −10, +10, +350]：排序完成:−170, −10, +10, +350。对应的人依次是 p1、p0、p3、p2。越靠前的人去 A 越划算,接下来前一半去 A、后一半去 B。
分配 · 前一半(N=2)去 A：N = 总人数 ÷ 2 = 2。排在前 2 位的 p1、p0 去 A(绿色),后 2 位暂时灰着,他们要去 B。
累加 · p1 去 A,+30：第一个去 A 的是 p1,加上他的 aCost = 30。总费用 total = 30。
累加 · p0 去 A,+10：第二个去 A 的是 p0,加上他的 aCost = 10。总费用累加到 total = 40。A 城名额满了。
A 城名额已满 · A 组小计 40：A 城两个名额已满,A 组小计 40(30 + 10)。接下来把后一半的人都送去 B。
分配 · 后一半去 B：剩下的 p3、p2 去 B(蓝色)。他们差值为正,本就去 B 更省。开始累加他们的 bCost。
累加 · p3 去 B,+20：p3 去 B,加上他的 bCost = 20。总费用 total = 60。
累加 · p2 去 B,+50：最后 p2 去 B,加上 bCost = 50。总费用累加到 total = 110。所有人都分配完了。
完成 · 最小总费用 = 110：答案 110!绿色去 A(40)、蓝色去 B(70)。按差值排序、前一半去 A,就拿到了全局最优。
为什么排序就一定最优?因为每个人去 A 相对去 B 的「净省」就是 −(aCost−bCost),要让 N 个去 A 的人净省最多,就该挑差值最小的 N 个——这正是排序前一半。
雷区实演 · 若按 aCost 排序就错了：假如按 aCost 排序:前两小是 p0(10)、p1(30) 去 A=40,p3、p2 去 B=70,这例恰好也得 110;但换一组数据(如有人 aCost 小却 bCost 更小)就会选错——必须用差值才稳。
边界三连：差值全相等时(如 [10,10])排序顺序不影响结果,任意分一半都对。
面试追问：能讲清「贪心为何对」并补一句 DP 兜底,是这题面试的加分项。
参考代码
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复杂度
- 时间复杂度：O(n log n)，主要开销在排序;之后一次线性遍历累加是 O(n),整体由排序主导
- 空间复杂度：O(1)，原地排序 + 几个累加变量;不计排序内部栈空间则为常数额外空间
易错点
面试追问把动画讲成自己的话
追问为什么贪心(差值排序)一定正确?
追问能不能用动态规划?
追问如果 A、B 名额不等(如 A 去 K 人)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
受标签影响的最大值
LeetCode 1090 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题