两地调度

关键问题:名额有限,该让谁去 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 兜底,是这题面试的加分项。