起因#

补ABC348C中，发现：

开二维数组空间时间双爆;
vector<pair<int, int>>操作过于麻烦。

于是翻题解，发现此知识漏洞，遂记录。

正文#

sort中的cmp函数#

sort函数在不使用cmp函数下，默认使用升序排序的cmp函数。我们需要对cmp函数稍加定义，即可实现自定义排序。
以下面的降序排序为例：

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5

6
bool cmp(int left, int right){
7
    return left > right;
8
}
9

10
signed main(){
11
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
12

13
    int a[8] = {1, 3, 2, 4, 6, 5, 7, 8};
14
    sort(a, a + 8, cmp);
15
    for(int i = 0; i < 8; i++)
16
        cout << a[i] << " ";
17
    return 0;
18
}

可以得到输出结果为：

1
8 7 6 5 4 3 2 1

结构体排序(分级排序)#

直接使用sort函数对结构体进行升序排序往往在算法竞赛中无法满足解题需求。cmp函数能够弥补这一问题。
以ABC348C为例。

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5

6
const int N = 2e5 + 5;
7
struct d{ //定义结构体
8
    int a, c;
9
} b[N];
10
int n;
11
int ans = 0;
12

13
bool cmp(d x, d y){ //cmp函数
14
    if(x.c == y.c) return x.a < y.a; //颜色相同,按照美味度升序排序
15
    else return x.c < y.c; //颜色不同,按照颜色升序排序
16
}
17

18
signed main(){
19
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
20

21
    //输入
22
    cin >> n;
23
    for(int i = 1; i <= n; i++)
24
        cin >> b[i].a >> b[i].c;
25

26
    sort(b + 1, b + n + 1, cmp); //排序
27
    for(int i = 1; i <= n; i++){
28
        if(b[i].c != b[i - 1].c) //如果颜色改变,此时b[i].a为颜色为b[i].c的豆子的最小美味度
29
            ans = max(ans, b[i].a); //记录所有豆子中最大的最小美味度
30
    }
31
    cout << ans << endl;
32
    return 0;
33
}

AC Record

另一道例题(P1104 生日)。
通过年、月、日、输入顺序的四层排序，能够非常简单地解决这一题。
其中cmp函数的if语句嵌套需要以符合自己的逻辑顺序的方法书写，否则容易思路打结。
AC Code:

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5

6
int n;
7
const int N = 105;
8
struct b{
9
    int id;
10
    string s;
11
    int y;
12
    int m;
13
    int d;
14
} a[N];
15

16
bool cmp(b left, b right){ //以年、月、日、输入顺序的顺序依次排序
17
    if(left.y == right.y){ //年份相等则进入下一层比较，不相等则得出比较顺序。月、日同理
18
        if(left.m == right.m){
19
            if(left.d == right.d){
20
                return left.id > right.id; //年月日全部相同，比较输入顺序
21
            } else {
22
                return left.d < right.d;
23
            }
24
        } else {
25
            return left.m < right.m;
26
        }
27
    } else {
28
        return left.y < right.y;
29
    }
30
}
31

32
signed main(){
33
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
34

35
    cin >> n;
36
    for(int i = 1; i <= n; i++){
37
        cin >> a[i].s >> a[i].y >> a[i].m >> a[i].d;
38
        a[i].id = i; //输入顺序需要手动标记
39
    }
40
    sort(a + 1,a + n + 1, cmp); //排序
41
    for(int i = 1; i <= n; i++){
42
        cout << a[i].s << endl;
43
    }
44
    return 0;
45
}