1029. Two City Scheduling

Two City Scheduling

題目描述：共有 2n 個人，costs[i] = [aCost, bCost] 表示第 i 人飛往城市 A 或城市 B 的費用。必須讓恰好 n 人去城市 A、n 人去城市 B，求最小總費用。

解題思路：

貪心策略：

關鍵思維轉換：先假設所有 2n 個人都去城市 A，總費用 = Σ aCost[i]。

接下來，我們要從中選出 n 個人「改去城市 B」，每個人改去 B 的額外費用 = bCost[i] - aCost[i]（可能為負，代表改去 B 反而更便宜）。

為了最小化總費用，我們應選差值最小（最划算改去 B）的 n 個人改派。

演算法步驟：

1. 計算基礎費用：所有人去城市 A 的總費用。
2. 計算每個人的「改派差值」diff[i] = bCost[i] - aCost[i]。
3. 按差值升序排序。
4. 選前 n 個人（差值最小的）改去城市 B，累加這 n 個差值到總費用。
5. 回傳最終總費用。

直觀理解：差值為負意味著「這個人去 B 比去 A 便宜」，優先讓這些人去 B；差值為正意味著「去 B 更貴」，但若必須湊足 n 人，也要從中選差值最小的。

範例說明：

costs = [[10,20],[30,200],[400,50],[30,20]]
基礎費用（全去 A）= 10 + 30 + 400 + 30 = 470
diff = [10, 170, -350, -10]（分別為 20-10, 200-30, 50-400, 20-30）
排序：[-350, -10, 10, 170]
選前 2 個改去 B：-350 + (-10) = -360
總費用：470 + (-360) = 110

時間複雜度：O(n log n) — 計算差值為 O(n)，排序為 O(n log n)，選取前 n 個為 O(n)，整體由排序主導（此處 n 指 costs.size() = 2n）。

空間複雜度：O(n) — 需要額外的差值陣列，大小為 2n。若直接對 costs 排序可降至 O(1)（排序 in-place）。

方法一：直接對 costs 排序（節省空間）

不建立額外的 diff 陣列，直接按差值對 costs 排序，前 n 人去城市 B，後 n 人去城市 A。

sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
    return (a[1] - a[0]) < (b[1] - b[0]);
});
int total = 0;
for (int i = 0; i < n; i++) total += costs[i][1];
for (int i = n; i < 2 * n; i++) total += costs[i][0];
return total;

時間複雜度 O(n log n)，空間複雜度 O(1)（忽略排序內部空間）。

方法二：動態規劃

定義 dp[i][j] 為前 i 個人中，有 j 個人去城市 A 的最小費用。狀態轉移：dp[i][j] = min(dp[i-1][j-1] + aCost[i], dp[i-1][j] + bCost[i])。

時間複雜度 O(n²)，空間複雜度 O(n²)（或用滾動陣列優化至 O(n)）。思路清晰但效率遜於貪心，適合初學者理解問題結構。

方法三：最小費用最大流（Min-Cost Max-Flow）

將問題建模為網路流：源點 → 每個人（容量 1）→ 城市 A 或城市 B（費用為對應 cost）→ 匯點（容量 n）。用 MCMF 演算法求解，正確但大幅過殺，時間複雜度 O(n³)，僅作學術了解用。

延伸問題

1. 若有 k 個城市（而非 2 個），各城市需要恰好 n 個人，如何求最小費用？ 這是「指派問題（Assignment Problem）」的推廣，貪心不再適用，需要用匈牙利演算法或最小費用最大流，時間複雜度為 O(n³) 或 O(n² log n)。

2. 若去城市 A 和城市 B 的人數不必相等（A 需要 a 人，B 需要 b 人，a + b = 2n），演算法是否仍然適用？ 完全適用，只需將「選前 n 個改去 B」改為「選前 b 個差值最小的改去 B」即可，核心貪心邏輯不變。

3. 此問題的貪心策略是否可以用交換論證（Exchange Argument）嚴格證明？ 是的：假設最優解中某個改去 B 的人的差值大於某個留在 A 的人，交換兩人的城市分配，總費用只會減少或不變，與最優假設矛盾。請嘗試寫出完整的形式化證明。