11.9 排序能解決哪些問題
會用 sort 之後，來看排序真正的價值：很多看起來跟排序無關的題目，排完序就變簡單了。這一節走三個經典場景，套路都是同一句話——排序後，該在一起的元素就在隔壁。
¶場景一：有幾個相異的數？
給 n 個數，問其中有幾個不同的數值。直覺做法：對每個數，往前檢查它出現過沒有——雙層迴圈，n 個數各檢查最多 n 次，運算量 O(n^2) 等級；n = 10^6 時約 10^{12} 次操作，用上冊 4.9 的基本法則（每秒約 10^9 次）一估——要跑千秒等級，死當。
換排序的思路：排序後，相同的數必定擠在一起。所以「新面孔」只會出現在「跟左邊那格不一樣」的位置：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1000005;
int a[MAX_N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n); // 排序後，相同的數全擠在一起
int ans = 1; // 第一個數必定是「新面孔」
for (int i = 1; i < n; i++) {
if (a[i] != a[i - 1]) ans++; // 跟左鄰不同 → 又一個新面孔
}
cout << ans << '\n';
return 0;
}
執行結果（輸入 8 與 3 1 2 5 1 2 2 3）：
4排序後是 1, 1, 2, 2, 2, 3, 3, 5——「跟左鄰不同」的位置有 3 處，加上開頭那個，相異數共 4 個。原本要「每個數跟所有數比」，排序後只要「每個數跟左鄰比」——O(n^2) 的比較塌縮成 O(n)，加上排序本身，總運算量由 sort 的 O(n \log n) 主導，n = 10^6 輕鬆過。
¶場景二：最接近的兩個數
給 n 個數，找出差距最小的一對。硬做是所有配對逐一算差距——又是 O(n^2)。但想一想：差距最小的一對，排序後必定相鄰。理由用三個數就能講完：若 a \le b \le c，則 c - a 既不小於 c - b、也不小於 b - a——隔著人的配對，差距永遠不會比相鄰配對更小。所以排序後只要掃一遍相鄰差：
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200005;
int a[MAX_N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n); // 排序後，最接近的兩個數必定相鄰
int best = a[1] - a[0];
for (int i = 2; i < n; i++) {
best = min(best, a[i] - a[i - 1]);
}
cout << best << '\n';
return 0;
}
執行結果（輸入 6 與 17 5 41 22 9 38）：
3排序後是 5, 9, 17, 22, 38, 41，相鄰差依序 4, 8, 5, 16, 3——最小是 38 與 41 的 3。注意排序後的差不用取絕對值（右邊一定不小於左邊），連 abs 都省了。
¶場景三：配對還原——最小配最小
n 個箱子、n 個蓋子，尺寸恰好一一對應，但兩堆各自被打亂了。怎麼把每個箱子配回它的蓋子？把兩邊各自排序：第 i 小的箱子，配的必然是第 i 小的蓋子——
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200005;
int box[MAX_N], lid[MAX_N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> box[i];
for (int i = 0; i < n; i++) cin >> lid[i];
sort(box, box + n); // 兩邊各自排序
sort(lid, lid + n);
for (int i = 0; i < n; i++) { // 第 i 小的箱子配第 i 小的蓋子
cout << box[i] << ' ' << lid[i] << '\n';
}
return 0;
}
執行結果（輸入 3、5 2 9、9 5 2）：
2 2
5 5
9 9「兩批東西要互相配對」的題目，十有八九從「兩邊各自排序」下手——最大配最大、最小配最小，順位對順位。
動手試試看：解掉相異數計數——就是場景一，但 n 到 10^6：雙層迴圈只拿得到部分分，滿分要用排序解法。題目敘述最下方附了輸入加速的提示，讀到最後別只看範例。