排序的隐藏维度:从"会排序"到"会用排序"的思维跃迁
开篇:关于排序,我们可能一直都理解错了
说实话,当我第一次看到”最优化调度”这种题的时候,我的第一反应是:这玩意儿和排序有什么关系?题面里连”排序”两个字都没提到。
然后我就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 导弹拦截
这题有两问:
- 一套系统最多能拦截多少导弹(高度非严格递减)
- 最少需要多少套系统才能拦截所有导弹
第一问:就是求最长非递增子序列(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
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:邻项交换法(暴力但有效)
前面国王游戏已经演示过了。这里再强调一遍核心步骤:
- 假设相邻两个元素i和j
- 分别计算”i在前”和”j在前”的代价/收益
- 列不等式:什么情况下”i在前”更优
- 化简不等式,得到排序关键字
适用范围:几乎所有贪心排序题。唯一的缺点是推导过程可能比较繁琐。
但是没关系,繁琐总比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个:~120mspartial_sort:~80msnth_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
前面说过了,不再重复。但真的有很多人会犯这个错误,包括我。
突破性总结:排序的本质不是”排”,而是”序”
初学者眼中的排序:把数组从小到大排列。
高手眼中的排序:建立一种顺序关系,让后续算法能够利用这种顺序。
具体来说:
- 降维:多维问题通过排序固定若干维度,降低复杂度
- 构造单调性:为二分、贪心、DP创造必要条件
- 优化搜索空间:改变搜索顺序,提升剪枝效率
- 建立映射:离散化、哈希的基础
最终的思维跃迁:
- 入门级:看到排序就调用
sort() - 进阶级:知道什么时候需要排序
- 高级:知道该排什么、怎么排
- 大师级:能设计排序策略来构造算法的正确性和高效性
当你做题时能够自然而然地想到”如果我先这样排序,后面的算法就能work了”,那就说明你真正掌握了排序在竞赛中的精髓。
至于我自己现在处于哪个级别?
大概在”进阶级偶尔掉线到入门级”的水平吧。毕竟昨天我还因为忘记排序WA了一题。
推荐练习题单
入门题(巩固识别能力):
进阶题(训练设计能力):
高级题(综合应用):
噩梦难度(仅供勇士):
如果你能把这些题都AC了,那么恭喜你,排序这一关基本通关。
如果还是WA,那就说明你和我一样,还需要继续修炼。
后记:关于这篇文章
写这篇文章的初衷,是因为我发现很多队友(包括我自己)在比赛中经常遇到”知道要排序,但不知道怎么排”的窘境。
网上的教程要么是纯理论,看完还是不会做题;要么是纯题解,看懂了这题,换个题还是不会。
所以我想写一篇”授人以渔”的文章,教大家如何系统性地思考排序问题。
至于写得好不好,就交给读者评判了。
如果你看完觉得有帮助,欢迎分享给队友。如果觉得写得不好,也欢迎在评论区指出问题。
毕竟我也是在学习的路上,能和大家一起进步就很好。
最后祝大家:
- 比赛不WA
- 排序不TLE
- 见题就会做
- AC如喝水
就这样。
如果这篇文章帮到了你,可以请我喝杯奶茶吗?(开玩笑的,点个赞就行)