TIP
贪心是一种比较短视的思想，即只在当前状态考虑最优解，最终就能取得全局最优解处理贪心问题，如果没有思路时，可以先尝试排序一下，考虑贪心做法有没有问题

区间问题#

区间选点#

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。

思路#

将每个区间按右端点从小到大排序
从前往后依次枚举每个区间，如果当前区间已经包含点，就跳过。否则选择当前区间的右端点

代码#

1
// Problem: 区间选点
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/907/
4
// Time: 2026-02-04 10:00:19
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 100010;
9

10
int n;
11
pair<int, int> section[N];
12
bool cmp(pair<int, int> &A, pair<int, int> &B) { return A.second < B.second; }
13

14
int main()
15
{
16
    cin >> n;
17

18
    for (int i = 0; i < n; i++)
19
    {
20
        int l, r;
21
        cin >> l >> r;
22
        section[i] = {l, r};
23
    }
24

25
    sort(section, section + n, cmp);
26

27
    int res = 0, ed = -2e9;
28
    for (int i = 0; i < n; i++)
29
    {
30
        if (section[i].first > ed)
31
        {
32
            res++;
33
            ed = section[i].second;
34
        }
35
    }
36

37
    cout << res << endl;
38
    return 0;
39
}

最大不相交区间数量#

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。

思路#

将每个区间按右端点从小到大排序
从前往后依次枚举每个区间，如果当前区间已经包含点，就跳过。否则选择当前区间的右端点
答案即为最大不相交区间数量。因为如果几个区间能被同一个点覆盖，就说明他们相交了，所以有几个选点，就有几个不相交区间

代码#

和区间选点的代码相同。

区间分组#

思路#

TIP
可以理解为：区间当成一个人占用某物品的时间，谁先来(左端点小)谁先上，哪个物品先用完(右端点小)先腾出来哪个

将所有区间按左端点从小到大排序
从前往后处理每个区间，依次判断能否将其放到某个现有的组中
用一个小根堆动态维护每个组的最右端点，heap.top() 即对应最小的最右端点

代码#

1
// Problem: 区间分组
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/908/
4
// Time: 2026-02-04 16:37:39
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 100010;
9

10
int n;
11
pair<int, int> s[N];
12

13
int main()
14
{
15
    cin >> n;
16
    for (int i = 0; i < n; i++)
17
    {
18
        int l, r;
19
        cin >> l >> r;
20
        s[i] = {l, r};
21
    }
22

23
    sort(s, s + n);
24

25
    priority_queue<int, vector<int>, greater<int>> heap;
26
    // 存储的是每个组的最右的端点，为了快速找出右侧端点最小的集合
27

28
    for (int i = 0; i < n; i++)
29
    {
30
        if (heap.empty() || heap.top() >= s[i].first) // 开一个新组，把这个区间放在新组的情况
31
            heap.push(s[i].second);
32

33
        else // 把这个区间放在组里的情况，只需要判断和右侧端点最小的那个组是否相交即可
34
        {
35
            heap.pop();
36
            heap.push(s[i].second);
37
        }
38
    }
39

40
    cout << heap.size() << endl;
41
    return 0;
42
}

区间覆盖#

思路#

将所有区间按左端点从小到大排序
从小到大枚举所有区间，在所有可以覆盖到 start 的区间里，选择右端点最大的区间
将 start 更新成右端点的最大值

代码#

1
// Problem: 区间覆盖
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/909/
4
// Time: 2026-02-04 21:55:00
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 100010;
9

10
int n, st, ed;
11
pair<int, int> s[N];
12

13
int main()
14
{
15
    cin >> st >> ed >> n;
16

17
    for (int i = 0; i < n; i++)
18
    {
19
        int l, r;
20
        cin >> l >> r;
21
        s[i] = {l, r};
22
    }
23

24
    sort(s, s + n);
25

26
    int res = 0;
27
    bool success = false;
28

29
    for (int i = 0; i < n; i++) // 枚举所有区间，注意左端点不是从0~n遍历，而是跳过了j已经遍历的点
30
    {
31
        // right应该在循坏里面定义，否则会把上一次的区间也算进去
32
        int j = i, r = -2e9;
33

34
        // 双指针，找到左端点在st之前的所有区间，并记录最大的右端点
35
        while (j < n && s[j].first <= st)
36
        {
37
            r = max(r, s[j].second);
38
            j++;
39
        }
40

41
        if (r < st) // 右端点在st之前，说明无法覆盖
42
        {
43
            res = -1;
44
            break;
45
        }
46

47
        res++; // 到这里还没跳出的话，说明找到了一个区间
48

49
        if (r >= ed) // 如果有个区间能覆盖end，说明能覆盖给定区间
50
        {
51
            success = true;
52
            break;
53
        }
54

55
        st = r;
56
        i = j - 1;
57
    }
58

59
    if (!success) // 遍历所有区间还没有覆盖到end的话，就没答案
60
        res = -1;
61

62
    cout << res << endl;
63

64
    return 0;
65
}

Huffman 树#

设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度。设 wi 为二叉树第 i 个叶节点的权值，li 为从根节点到第 i 个叶节点的路径长度，则树的带权路径长度为： $WPL = \sum_{i=1}^n w_i l_i$ 对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树称为霍夫曼树（Huffman Tree）对于霍夫曼树来说，其叶结点权值越小，离根越远，叶结点权值越大，离根越近，此外整棵树中仅有叶结点的度为 0，其他结点度均为 2

合并果子#

思路#

代码#

1
// Problem: 合并果子
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/150/
4
// Time: 2026-02-04 22:33:13
5
// 注意本题允许合并不连续的各堆果子，而区间dp的合并石子是连续的
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
int main()
10
{
11
    int n;
12
    cin >> n;
13

14
    priority_queue<int, vector<int>, greater<int>> heap;
15

16
    while (n--)
17
    {
18
        int x;
19
        cin >> x;
20
        heap.push(x);
21
    }
22

23
    int res = 0;
24
    while (heap.size() > 1)
25
    {
26
        int a = heap.top();
27
        heap.pop();
28
        int b = heap.top();
29
        heap.pop();
30

31
        res += (a + b);
32
        heap.push(a + b);
33
    }
34

35
    cout << res << endl;
36
    return 0;
37
}

合并果子加强版#

2026 牛客寒假集训营 5-D 本题思路：每次找出重量的最小值，先在这堆内部合并，如果最后剩一堆，就尝试和次小值合并，用 map 维护整个过程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int mod = 1e9 + 7;
4
const int N = 1e5 + 10;
5
typedef long long ll;
6

7
map<ll, ll> mp; // weight - count
8
ll res;
9

10
int main()
11
{
12
    int n;
13
    cin >> n;
14

15
    for (int i = 1; i <= n; i++)
16
    {
17
        ll c, w;
18
        cin >> c >> w;
19

20
        mp[w] += c;
21
    }
22

23
    while (mp.size() > 1 || (mp.size() == 1 && mp.begin()->second > 1))
24
    {
25
        auto it = mp.begin();
26

27
        ll wgt = it->first, cnt = it->second;
28
        if (cnt >= 2)
29
        {
30
            ll merge_times = cnt / 2;
31

32
            ll tmp = ((wgt % mod) * 2) % mod;
33
            tmp = tmp * (merge_times % mod) % mod;
34
            res = (res + tmp) % mod;
35

36
            mp[2 * wgt] += merge_times;
37

38
            if (cnt % 2 == 0)
39
                mp.erase(it);
40
            else
41
                it->second = 1;
42
        }
43

44
        else // cnt == 1
45
        {
46
            auto ne = next(it);
47

48
            ll wgt2 = ne->first, cnt2 = ne->second;
49

50
            ll tmp = (wgt2 % mod + wgt % mod) % mod;
51
            res = (res + tmp) % mod;
52

53
            mp[wgt2 + wgt] += 1;
54

55
            mp.erase(it);
56
            if (cnt2 == 1)
57
                mp.erase(ne);
58
            else
59
                ne->second -= 1;
60
        }
61
    }
62

63
    cout << res << endl;
64
    return 0;
65
}

排序不等式#

排队打水#

思路#

代码#

1
// Problem: 排队打水
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/description/915/
4
// Time: 2026-02-05 16:37:52
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 100010;
10

11
int a[N];
12
int n;
13
long long res;
14

15
int main()
16
{
17
    cin >> n;
18
    for (int i = 1; i <= n; i++)
19
        cin >> a[i];
20

21
    sort(a + 1, a + n + 1);
22

23
    for (int i = 1; i <= n; i++)
24
    {
25
        int j = n - i;
26
        res += a[i] * j;
27
    }
28

29
    cout << res << endl;
30
    return 0;
31
}

绝对值不等式#

货仓选址#

思路#

代码#

1
// Problem: 货仓选址
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/106/
4
// Time: 2026-02-05 17:30:03
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
const int N = 100010;
10

11
int n;
12
int a[N];
13
int res;
14

15
int main()
16
{
17
    cin >> n;
18

19
    for (int i = 0; i < n; i++)
20
        cin >> a[i];
21

22
    sort(a, a + n);
23

24
    for (int i = 0; i < n; i++)
25
    {
26
        res += abs(a[n >> 1] - a[i]);
27
    }
28

29
    cout << res << endl;
30
    return 0;
31
}

贪心递推公式#

耍杂技的牛#

思路#

代码#

1
// Problem: 耍杂技的牛
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/127/
4
// Time: 2026-02-05 17:53:05
5
// 存在结论：按照w[i] + s[i]从小到大的顺序排，最大的危险系数一定最小
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9
typedef pair<int, int> PII;
10
const int N = 50010;
11

12
int n;
13
PII cow[N];
14

15
int main()
16
{
17
    cin >> n;
18
    for (int i = 0; i < n; i++)
19
    {
20
        int w, s;
21
        cin >> w >> s;
22
        cow[i] = {w + s, w}; // 存储每头牛的w+s的总和
23
    }
24

25
    sort(cow, cow + n);
26
    int res = -2e9, sum = 0;
27
    for (int i = 0; i < n; i++)
28
    {
29
        int w = cow[i].second, s = cow[i].first - w;
30
        res = max(res, sum - s); // 计算每头牛的风险值并取最大
31
        sum += w; // 总重量
32
    }
33

34
    cout << res << endl;
35
    return 0;
36
}