排序的隐藏维度:从"会排序"到"会用排序"的思维跃迁

开篇:关于排序,我们可能一直都理解错了

说实话,当我第一次看到”最优化调度”这种题的时候,我的第一反应是:这玩意儿和排序有什么关系?题面里连”排序”两个字都没提到。

然后我就WA了。改了三次,还是WA。最后看题解的时候,发现第一行就是 sort(a, a+n, cmp)

我当场裂开。

后来我逐渐意识到一个残酷的真相:从小学到大的排序训练,都是”给你一堆数字,从小到大排”。但ICPC考的是在完全看不出来要排序的情况下,你能否主动发现排序的必要性,并且设计出正确的排序策略

这就好比你学了十年如何使用锤子钉钉子,结果考试题目是:”请设计一个工具来固定木板”。题目里根本没提锤子,但你得自己意识到需要用锤子,而且还得想清楚往哪儿钉、怎么钉。

所以这篇文章要做的事情很简单:教你如何在题目没有明说的情况下,嗅出排序的味道

顺便说一句,如果你看完这篇文章还是不会,那可能是我写得不好。欢迎在评论区喷我,但请文明用语,毕竟我玻璃心。


第一维度:识别 - 那些藏得很深的排序信号

信号1:贪心题里的”先后顺序学”

很多贪心题的本质其实就一句话:先干谁,后干谁

而这个”先后”,90%的情况下就是靠排序决定的。剩下10%是因为题目太简单,根本不需要贪心。

案例1:洛谷 P1080 国王游戏

国王和n个大臣排成一排发奖金。第i个大臣的奖金 = 前面所有人左手数字的乘积 ÷ 自己右手的数字。问怎么排列大臣能让最大奖金尽可能小。

第一次看到这题我的思路是:按左手排?不对。按右手排?也不对。按左手×右手?试试看?

结果全错。

正确思路:相邻两个大臣i和j,如果交换他们对答案更优,会发生什么?

假设前面的累积乘积是P:

  • i在前面:两人中的最大奖金是 $\max(\frac{P}{b_i}, \frac{P \cdot a_i}{b_j})$
  • j在前面:两人中的最大奖金是 $\max(\frac{P}{b_j}, \frac{P \cdot a_j}{b_i})$

为了让i排前面更优,需要: \(\frac{P \cdot a_i}{b_j} \leq \frac{P \cdot a_j}{b_i}\)

化简一下(P可以约掉): \(a_i \cdot b_i \leq a_j \cdot b_j\)

所以答案是:按左手×右手从小到大排序

看到这里你可能会问:这谁能想到啊?

答案是:想不到的话,就用邻项交换法暴力推导。这个方法简单粗暴,就是假设相邻两个元素交换位置,看看哪种情况更优,然后列不等式。虽然过程有点繁琐,但至少不用靠”灵光一现”。

毕竟灵光一现这种事,一般只在WA了5次之后才会发生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

struct Minister {
    int left, right;
    bool operator<(const Minister& other) const {
        return left * right < other.left * other.right;
    }
};

int main() {
    int n;
    cin >> n;
    Minister king;
    cin >> king.left >> king.right;
    
    vector<Minister> ministers(n);
    for (int i = 0; i < n; i++) {
        cin >> ministers[i].left >> ministers[i].right;
    }
    
    sort(ministers.begin(), ministers.end());
    
    // 接下来是高精度计算部分,这里省略
    // 因为重点是排序,不是高精度(虽然高精度也很折磨人)
    
    return 0;
}

冷知识:这题如果你用 long long 会爆,用 unsigned long long 也会爆,最后只能用高精度。所以排序只是第一关,后面还有更大的坑在等你。

案例2:洛谷 P1803 凌乱的yyy / 线段覆盖

有n个活动,每个活动有开始和结束时间,选最多的不冲突活动。

这题是经典的区间调度问题。标准答案是按结束时间从早到晚排序

但为什么呢?为什么不是按开始时间排?为什么不是按持续时间排?

简单证明: 假设最优解里第一个被选中的活动不是最早结束的,叫它A。现在把A换成最早结束的活动B。

因为B结束得更早,所以B后面能接的活动至少和A一样多(甚至可能更多)。所以这个替换不会让答案变差。

这个证明看起来很抽象,但背后的直觉很简单:越早结束,后面的选择余地越大

就像你相亲一样,越早结束一场相亲,后面能约的人就越多。虽然这个比喻可能不太恰当,但确实挺形象的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

struct Activity {
    int start, end;
    bool operator<(const Activity& other) const {
        return end < other.end; // 按结束时间排序
    }
};

int main() {
    int n;
    cin >> n;
    vector<Activity> acts(n);
    for (int i = 0; i < n; i++) {
        cin >> acts[i].start >> acts[i].end;
    }
    
    sort(acts.begin(), acts.end());
    
    int count = 1, lastEnd = acts[0].end;
    for (int i = 1; i < n; i++) {
        if (acts[i].start >= lastEnd) {
            count++;
            lastEnd = acts[i].end;
        }
    }
    
    cout << count << endl;
    return 0;
}

补充说明:这题如果按开始时间排序会WA得很惨。我知道是因为我WA过。


信号2:DP里的”依赖关系排序”

DP本质上是在有向无环图(DAG)上做递推。而排序的作用,就是帮你找到一个合法的拓扑序,让你能按正确的顺序计算状态。

听起来很高大上,其实就是:先算能算的,再算依赖它的

案例3:洛谷 P1020 导弹拦截

这题有两问:

  1. 一套系统最多能拦截多少导弹(高度非严格递减)
  2. 最少需要多少套系统才能拦截所有导弹

第一问:就是求最长非递增子序列(LIS变种)。经典的 $O(n \log n)$ 做法,用二分 + 贪心。

1
2
3
4
5
6
7
8
9
10
11
12
int maxIntercept(vector<int>& missiles) {
    vector<int> dp; // dp[i] 表示长度为i+1的LIS的最小结尾值
    for (int m : missiles) {
        auto it = lower_bound(dp.begin(), dp.end(), m, greater<int>());
        if (it == dp.end()) {
            dp.push_back(m);
        } else {
            *it = m;
        }
    }
    return dp.size();
}

第二问:这里有个神奇的定理叫Dilworth定理 - 最少链覆盖数 = 最长反链长度。

翻译成人话就是:最少需要的系统数 = 最长严格递增子序列的长度

所以第二问只需要把第一问的 greater<int>() 去掉就行了。

1
2
3
4
5
6
7
8
9
10
11
12
int minSystems(vector<int>& missiles) {
    vector<int> dp;
    for (int m : missiles) {
        auto it = upper_bound(dp.begin(), dp.end(), m);
        if (it == dp.end()) {
            dp.push_back(m);
        } else {
            *it = m;
        }
    }
    return dp.size();
}

冷知识:Dilworth定理是1950年提出的,比很多OIer的爷爷还老。但它在竞赛里的出场率依然很高,堪称”老当益壮”的典范。

案例4:洛谷 P1233 木棍加工

n根木棍,每根有长度L和重量W。加工必须从长到短、从重到轻。求最少需要几次加工。

这题第一眼看上去毫无头绪。但仔细一想:

  1. 长度和重量都有限制,这是个二维偏序问题
  2. 按长度从大到小排序,把一个维度固定住
  3. 在重量这个维度上求最长递减子序列
  4. 答案就是这个子序列的长度

为什么?因为最长递减子序列可以一次加工完,其他的木棍必须分到别的加工次数里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

struct Stick {
    int length, weight;
    bool operator<(const Stick& other) const {
        if (length != other.length) return length > other.length;
        return weight > other.weight; // 长度相同时按重量降序
    }
};

int main() {
    int n;
    cin >> n;
    vector<Stick> sticks(n);
    for (int i = 0; i < n; i++) {
        cin >> sticks[i].length >> sticks[i].weight;
    }
    
    sort(sticks.begin(), sticks.end());
    
    // 在weight维度上求最长递减子序列
    vector<int> dp;
    for (auto& s : sticks) {
        auto it = lower_bound(dp.begin(), dp.end(), s.weight, greater<int>());
        if (it == dp.end()) {
            dp.push_back(s.weight);
        } else {
            *it = s.weight;
        }
    }
    
    cout << dp.size() << endl;
    return 0;
}

注意:排序时如果长度相同,必须按重量降序排。否则会出现”长度一样但重量不一样”的木棍被错误地归为一组,然后你就WA了。

(别问我怎么知道的。)


信号3:二分答案里的”单调性构造”

二分答案的核心是check函数要有单调性。而很多时候,这个单调性需要先排序才能构造出来。

案例5:洛谷 P1873 砍树

n棵树,高度为 $h_i$。设定锯子高度H,砍掉所有超过H的部分。求能获得至少m长度木材的最大H值。

分析:H越小,砍下来的木材越多。这是天然的单调性,不需要排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

long long getCut(vector<int>& trees, int H) {
    long long total = 0;
    for (int h : trees) {
        if (h > H) total += h - H;
    }
    return total;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> trees(n);
    for (int i = 0; i < n; i++) {
        cin >> trees[i];
    }
    
    int left = 0, right = *max_element(trees.begin(), trees.end());
    int ans = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (getCut(trees, mid) >= m) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

这题确实不需要排序。但我放在这里是为了对比:有些二分题不需要排序,有些则必须先排序

案例6:洛谷 P1316 丢瓶盖

数轴上有n个点,选m个服务点,最小化”点到最近服务点的最大距离”。

这题就必须先排序。因为check函数需要贪心地放置服务点:从左到右扫描,当前位置放一个服务点,下一个服务点尽可能往右放(距离不超过2d)。

如果不排序,这个贪心策略根本没法实施。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

bool canCover(vector<int>& points, int m, int d) {
    int count = 1;
    int lastPos = points[0];
    
    for (int i = 1; i < points.size(); i++) {
        if (points[i] - lastPos > d) {
            count++;
            lastPos = points[i];
            if (count > m) return false;
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i];
    }
    
    sort(points.begin(), points.end()); // 不排序直接爆炸
    
    int left = 0, right = points.back() - points.front();
    int ans = right;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canCover(points, m, mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

总结:二分答案见到”数轴上的点”、”区间覆盖”这种关键词,99%要先排序。


信号4:离散化里的”值域压缩”

当题目给的数据范围是 $10^9$,但数据个数只有 $10^5$ 时,你就应该条件反射般地想到:离散化

而离散化的第一步,就是排序。

案例7:洛谷 P1908 逆序对

统计有多少对 $(i, j)$ 满足 $i < j$ 且 $a_i > a_j$。

方法1:归并排序(隐式利用排序的性质)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
long long mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return 0;
    
    int mid = l + (r - l) / 2;
    long long cnt = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r);
    
    vector<int> temp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            temp.push_back(arr[j++]);
            cnt += mid - i + 1; // 关键:统计逆序对
        }
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= r) temp.push_back(arr[j++]);
    
    for (int i = l; i <= r; i++) {
        arr[i] = temp[i - l];
    }
    return cnt;
}

方法2:树状数组 + 离散化(显式排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

class BIT {
    vector<int> tree;
    int n;
public:
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, int val) {
        for (; i <= n; i += i & -i) tree[i] += val;
    }
    
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 离散化
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    
    for (int& x : arr) {
        x = lower_bound(sorted_arr.begin(), sorted_arr.end(), x) - sorted_arr.begin() + 1;
    }
    
    BIT bit(sorted_arr.size());
    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += i - bit.query(arr[i]); // 前面有多少个比它大
        bit.update(arr[i], 1);
    }
    
    cout << cnt << endl;
    return 0;
}

冷知识:离散化的本质是建立”原值 → 排名”的映射。就像高考成绩排名一样,750分的人排第1,700分的人可能排第100,中间那些分数没人考也无所谓。


信号5:搜索剪枝里的”顺序优化”

这个比较玄学,但确实有效:搜索时先处理”限制大的”选项,可以更早剪枝

案例8:洛谷 P1441 砝码称重

n个砝码,去掉m个,问剩下的能称出多少种重量。

暴力做法:枚举去掉哪m个,每种情况用bitset算可达状态。

优化:砝码按重量从大到小排序。因为大砝码的”影响力”更大,先去掉大砝码更容易产生不同的结果,搜索树会更”分散”,剪枝效果更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> weights;
set<bitset<100001>> visited;

void dfs(int idx, vector<bool>& used, int removed) {
    if (removed == m) {
        bitset<100001> reachable;
        reachable[0] = 1;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                reachable |= (reachable << weights[i]);
            }
        }
        visited.insert(reachable);
        return;
    }
    
    if (idx == n) return;
    
    dfs(idx + 1, used, removed);
    
    used[idx] = true;
    dfs(idx + 1, used, removed + 1);
    used[idx] = false;
}

int main() {
    cin >> n >> m;
    weights.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    
    sort(weights.begin(), weights.end(), greater<int>()); // 从大到小
    
    vector<bool> used(n, false);
    dfs(0, used, 0);
    
    int maxCount = 0;
    for (auto& bs : visited) {
        maxCount = max(maxCount, (int)bs.count() - 1);
    }
    
    cout << maxCount << endl;
    return 0;
}

说实话:这种优化效果因题而异,有时候根本看不出差别。但不妨碍我们装作很懂的样子写进代码里。


第二维度:设计 - 如何不靠猜地找到排序关键字

技巧1:邻项交换法(暴力但有效)

前面国王游戏已经演示过了。这里再强调一遍核心步骤:

  1. 假设相邻两个元素i和j
  2. 分别计算”i在前”和”j在前”的代价/收益
  3. 列不等式:什么情况下”i在前”更优
  4. 化简不等式,得到排序关键字

适用范围:几乎所有贪心排序题。唯一的缺点是推导过程可能比较繁琐。

但是没关系,繁琐总比WA强

技巧2:反向构造法(从终态倒推)

案例9:洛谷 P1106 删数问题

给定n位数,删除k位,使剩余数字最小。

直觉思路:从左到右,遇到”后面的数字比当前数字小”的情况,就删掉当前数字。

这个思路本质上是在维护一个单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int main() {
    string num;
    int k;
    cin >> num >> k;
    
    string result;
    for (char digit : num) {
        while (!result.empty() && k > 0 && result.back() > digit) {
            result.pop_back();
            k--;
        }
        result.push_back(digit);
    }
    
    // 如果还没删够,从后面删
    while (k > 0) {
        result.pop_back();
        k--;
    }
    
    // 去除前导0
    int start = 0;
    while (start < result.size() && result[start] == '0') {
        start++;
    }
    
    string ans = (start == result.size()) ? "0" : result.substr(start);
    cout << ans << endl;
    
    return 0;
}

冷知识:这题如果用贪心直接选”保留最小的k位”会WA。比如 “54321” 删2位,答案是 “321” 而不是 “321”… 等等,这俩一样?

好吧,换个例子:”1432219” 删3位,答案是 “1219” 而不是 “1129”。

总之,这题得用单调栈。


第三维度:优化 - 当常规排序不够快时

优化1:利用数据特性换排序算法

场景1:值域很小 → 计数排序 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
void countingSort(vector<int>& arr, int maxVal) {
    vector<int> count(maxVal + 1, 0);
    for (int x : arr) count[x]++;
    
    int idx = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]--) {
            arr[idx++] = i;
        }
    }
}

适用场景:数据范围在10^6以内,且数据量也不大。

不适用场景:数据范围10^9。因为开不了那么大的数组,会MLE。

场景2:01序列 → partition $O(n)$

1
2
3
4
5
6
7
8
void sort01(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        while (left < right && arr[left] == 0) left++;
        while (left < right && arr[right] == 1) right--;
        if (left < right) swap(arr[left++], arr[right--]);
    }
}

冷知识:这其实就是快排的partition部分。所以快排的本质是”递归地partition”。

优化2:部分排序

案例10:洛谷 P1923 求第k小的数

最优解nth_element,期望复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    nth_element(arr.begin(), arr.begin() + k, arr.end());
    
    cout << arr[k] << endl;
    return 0;
}

性能对比(n=10^6):

  • sort 然后取第k个:~120ms
  • partial_sort:~80ms
  • nth_element:~40ms

结论:能用 nth_element 的时候千万别用 sort。毕竟能偷懒为什么不偷。

优化3:避免重复排序

1
2
3
4
5
6
7
8
9
10
11
12
// 错误示范:每次查询都排序
for (int q = 0; q < Q; q++) {
    vector<int> temp = data;
    sort(temp.begin(), temp.end());
    // 处理查询...
}

// 正确做法:只排序一次
sort(data.begin(), data.end());
for (int q = 0; q < Q; q++) {
    // 处理查询...
}

真实故事:我曾经一道题因为在循环里写了 sort,导致TLE了3次。后来把 sort 提到循环外面,直接AC。

当时的心情就一个字:

优化4:自定义比较器的性能陷阱

1
2
3
4
5
6
7
8
9
10
11
// 错误:每次比较都调用耗时函数
sort(arr.begin(), arr.end(), [](int a, int b) {
    return expensiveFunction(a) < expensiveFunction(b);
});

// 正确:预计算
vector<pair<int, int>> temp;
for (int x : arr) {
    temp.push_back({expensiveFunction(x), x});
}
sort(temp.begin(), temp.end());

血泪教训expensiveFunction 如果是 $O(n)$ 的,那么整个排序就变成了 $O(n^2 \log n)$。然后你就TLE了。


综合实战:终极Boss战

案例11:洛谷 P1090 合并果子

n堆果子,每次合并两堆,代价=两堆数量之和。求最小总代价。

表面:经典的Huffman编码问题,用优先队列。

深层:为什么每次选最小的两堆合并?这背后就是排序思想。

证明:假设有三堆果子a ≤ b ≤ c。如果先合并b和c,代价是 (b+c) + (a+b+c)。如果先合并a和b,代价是 (a+b) + (a+b+c)。显然后者更小。

所以策略就是:每次都合并最小的两堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }
    
    long long cost = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        cost += a + b;
        pq.push(a + b);
    }
    
    cout << cost << endl;
    return 0;
}

升维思考:优先队列本质上就是在动态维护有序性。每次pop最小元素,就相当于在做部分排序。

所以说到底,还是排序。


思维框架总结:排序决策三部曲

当你拿到一道题,不确定是否需要排序时,按这个流程走:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
第一步:识别信号
├─ 关键词:"最多"、"最少"、"最优" → 可能需要贪心+排序
├─ 状态转移有依赖 → DP可能需要预排序
├─ 涉及查找、二分 → 必须先排序
├─ 数据范围大但稀疏 → 离散化(排序)
└─ 搜索题但数据有特征 → 考虑排序优化剪枝

第二步:设计关键字
├─ 邻项交换法 → 列不等式倒推
├─ 反向构造法 → 从目标状态反推
├─ 多维偏序 → 固定若干维度,剩余维度做DP
└─ 实在想不出来 → 试试按题目给的各个属性排序,提交看看

第三步:选择算法
├─ 值域小 → 计数排序 O(n)
├─ 只需部分有序 → nth_element / partial_sort
├─ 需要稳定性 → stable_sort
├─ 动态维护有序 → 优先队列、平衡树
└─ 常规情况 → sort

常见错误与避坑指南

错误1:比较器写错导致RE

1
2
3
4
// 危险!违反严格弱序
sort(arr.begin(), arr.end(), [](int a, int b) {
    return a <= b; // 错误!应该用 <
});

后果:程序可能崩溃,或者得到错误结果。而且不同编译器表现不一致,本地能过,OJ上RE。

正确写法:永远用 <,不要用 <=

错误2:多关键字排序的顺序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
// 错误:先按成绩排,再按年龄排,会破坏成绩的顺序
sort(students.begin(), students.end(), cmpByScore);
sort(students.begin(), students.end(), cmpByAge);

// 正确方法1:用stable_sort
stable_sort(students.begin(), students.end(), cmpByScore);
stable_sort(students.begin(), students.end(), cmpByAge);

// 正确方法2:一次性比较(推荐)
sort(students.begin(), students.end(), [](auto& a, auto& b) {
    if (a.age != b.age) return a.age < b.age;
    return a.score > b.score;
});

错误3:忘记离散化导致MLE

1
2
3
4
5
6
7
// 数据范围1e9,直接开数组会爆
int cnt[1000000000]; // MLE!

// 正确:先离散化
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
// 现在arr.size()可能只有1e5,可以安全使用

错误4:在循环里重复排序导致TLE

前面说过了,不再重复。但真的有很多人会犯这个错误,包括我。


突破性总结:排序的本质不是”排”,而是”序”

初学者眼中的排序:把数组从小到大排列。

高手眼中的排序:建立一种顺序关系,让后续算法能够利用这种顺序

具体来说:

  1. 降维:多维问题通过排序固定若干维度,降低复杂度
  2. 构造单调性:为二分、贪心、DP创造必要条件
  3. 优化搜索空间:改变搜索顺序,提升剪枝效率
  4. 建立映射:离散化、哈希的基础

最终的思维跃迁

  • 入门级:看到排序就调用 sort()
  • 进阶级:知道什么时候需要排序
  • 高级:知道该排什么、怎么排
  • 大师级:能设计排序策略来构造算法的正确性和高效性

当你做题时能够自然而然地想到”如果我先这样排序,后面的算法就能work了”,那就说明你真正掌握了排序在竞赛中的精髓。

至于我自己现在处于哪个级别?

大概在”进阶级偶尔掉线到入门级”的水平吧。毕竟昨天我还因为忘记排序WA了一题。


推荐练习题单

入门题(巩固识别能力):

进阶题(训练设计能力):

高级题(综合应用):

噩梦难度(仅供勇士):

如果你能把这些题都AC了,那么恭喜你,排序这一关基本通关。

如果还是WA,那就说明你和我一样,还需要继续修炼。


后记:关于这篇文章

写这篇文章的初衷,是因为我发现很多队友(包括我自己)在比赛中经常遇到”知道要排序,但不知道怎么排”的窘境。

网上的教程要么是纯理论,看完还是不会做题;要么是纯题解,看懂了这题,换个题还是不会。

所以我想写一篇”授人以渔”的文章,教大家如何系统性地思考排序问题

至于写得好不好,就交给读者评判了。

如果你看完觉得有帮助,欢迎分享给队友。如果觉得写得不好,也欢迎在评论区指出问题。

毕竟我也是在学习的路上,能和大家一起进步就很好。

最后祝大家:

  • 比赛不WA
  • 排序不TLE
  • 见题就会做
  • AC如喝水

就这样。


如果这篇文章帮到了你,可以请我喝杯奶茶吗?(开玩笑的,点个赞就行)