贪心算法

区间问题

区间覆盖问题

题目描述

给定 $N$ 个闭区间 $[a_i, b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
注意：位于区间端点上的点也算作区间内。

输入格式

  • 第一行包含一个整数 $N$，表示区间的数量。
  • 接下来 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

  • $1 \leq N \leq 10^5$
  • $-10^9 \leq a_i \leq b_i \leq 10^9$

输入样例

1
2
3
4
5
4
1 3
2 4
5 7
6 8

输出样例

1
2

解题思路

区间按右端点非递减排序，每次选取右端点。

证明

假设最优解是 $res$ ，贪心算法的解是 $cnt$ ，那么有: $res \leq cnt$ ；按照贪心算法，只有区间不相交时才会选取，意即至少有 $cnt$ 个不相交的区间，至少需要 $cnt$ 个点，那么有 $res \ge cnt$ ；因此 $res = cnt$ 。

Code

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n;

bool cmp(pair<int,int> a, pair<int,int> b) {
    return a.second < b.second;
}

int main() {
    cin >> n;
    int a, b;
    vector<pair<int,int>> segs;
    for(int i = 0; i < n; ++ i) {
        cin >> a >> b;
        segs.push_back(make_pair(a, b));
    }
    sort(segs.begin(), segs.end(), cmp);
    int ed = -2e9, res = 0;
    for(auto seg: segs) 
        if(ed < seg.first) ++ res, ed = seg.second;
    cout << res << endl;
    return 0;
}

区间调度问题

题目描述

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

输入格式

  • 第一行包含一个整数 $N$，表示区间数。
  • 接下来 $N$ 行，每行包含两个整数 $a_i, b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示可选取的区间的最大数量。

数据范围

  • $1 \leq N \leq 10^5$
  • $-10^9 \leq a_i \leq b_i \leq 10^9$

输入样例

1
2
3
4
3
-1 1
2 4
3 5

输出样例

1
2

解题思路

以右端点非递减排序，遍历，每次比较当前区间的左端点与 $ed$ ，若大于，则选择。

证明

假设最优解与贪心解分别为 $res, cnt$ , 那么有 $res \ge cnt$；考虑 $cnt$ 的求法，每一个选中的区间必然 $pass$ 掉若干右端点比它大的区间，并且这些区间的左端点小于该区间的右端点，将这些区间看成一个集合，因此共有 $cnt$ 个集合，每一个集合内的区间都两两相交；根据抽屉原理，若 $ans \gt cnt$ ，则 $ans$ 中必然有两个区间在同一个集合，矛盾，因此 $ans \le cnt$， 因此 $ans = cnt$。

Code

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 <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;

#define x first
#define y second

bool cmp(PII a, PII b) {
    return a.y < b.y;
}

int n, a, b;
vector<PII> segs;

int main() {
    cin >> n;
    for(int i = 0; i < n; ++ i) {cin >> a >> b; segs.push_back(make_pair(a, b));}
    sort(segs.begin(), segs.end(), cmp);
    int st, ed;
    st = ed = -2e9;
    int res = 0;
    for(auto seg: segs) {
        if(ed < seg.x) ++ res, st = seg.x, ed = seg.y;
    }
    cout << res << endl;
    return 0;
}

区间分组问题

题目描述

给定 $N$ 个闭区间 $[a_i, b_i]$，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。

输入格式

  • 第一行包含整数 $N$，表示区间数量。
  • 接下来 $N$ 行，每行包含两个整数 $a_i, b_i$，表示一个区间的左右端点。

输出格式

输出一个整数，表示将所有区间分组后的最小组数。

数据范围

  • $1 \le N \le 10^5$
  • $-10^9 \le a_i \le b_i \le 10^9$

输入样例

1
2
3
4
3
-1 1
2 4
3 5

输出样例

1
2

解题思路

将区间按照左端点排序，遍历，每次判断该区间是否能放入某个集合，若不能，则新开一个集合；对于每个集合，维护一个最大右端点值，由于是以左端点排序，那么只要当前遍历到的区间的左端点大于右端点，就能放入到该集合内；进一步的，维护所集合的最右端点值，每次尽可能放入具有最小右端点值的集合。

证明思路

按照算法，每次引起新建集合的区间必定和当前集合的所有区间两两相交，因此至少需要 $cnt$ 个集合，有 $res \ge cnt$;

Code

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 <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

struct e{
    int l, r;
    bool operator < (const e &w)const{
        return l < w.l;
    }
}segs[N];

int n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> segs[i].l >> segs[i].r;
    sort(segs + 1, segs + n + 1);
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 1; i <= n; ++ i) {
        if(heap.empty() || heap.top() >= segs[i].l) heap.push(segs[i].r);
        else heap.pop(), heap.push(segs[i].r);
    }
    cout << heap.size() << endl;
    return 0;
}

区间覆盖问题（指定区间完全覆盖）

题目描述

给定 $N$ 个区间 $[a_i, b_i]$ 以及一个目标区间 $[s, t]$，请你从这 $N$ 个区间中选择尽量少的区间，使得所选区间的并集能够完全覆盖目标区间 $[s, t]$。如果无法覆盖则输出 $-1$。

输入格式

  • 第一行包含两个整数 $s$ 和 $t$，表示目标区间的左右端点。
  • 第二行包含一个整数 $N$，表示给定区间的数量。
  • 接下来 $N$ 行，每行包含两个整数 $a_i, b_i$，表示第 $i$ 个区间的左右端点。

输出格式

输出一个整数，表示所需的最少区间数量；如果无法完全覆盖则输出 -1。

数据范围

  • $1 \le N \le 10^5$
  • $-10^9 \le a_i \le b_i \le 10^9$
  • $-10^9 \le s \le t \le 10^9$

输入样例

1
2
3
4
5
1 5
3
-1 3
2 4
3 5

输出样例

1
2

解题思路

以左端点排序，每次选择尽可能覆盖更多的区间。

证明

按照算法，每次选择的都是左端点小于 $st$ ，右端点尽可能大的区间；如果 $ans \lt cnt$ , 那么 $cnt$ 中必然至少有两个区间可以被一个区间代替，这与算法矛盾，因为这样的区间必然会被算法在前次遍历时选取，因此 $an \ge cnt$

Code

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;

PII segs[N];

#define x first
#define y second

bool cmp(PII a, PII b) {
    return a.x < b.x;
}

int main() {
    int st, ed, n;
    cin >> st >> ed >> n;
    for(int i = 1; i <= n; ++ i) {
        cin >> segs[i].x >> segs[i].y;
    }
    sort(segs + 1, segs + n + 1);
    int res = 0;
    bool success = false;;
    for(int i = 1; i <= n; ++ i) {
        int j = i, b = -2e9;
        while(j <= n && segs[j].x <= st) {
            b = max(b, segs[j].y);
            ++ j;
        }
        if(b < st) {success = false; break;}
        ++ res;
        if(b >= ed) {success = true; break;}
        st = b, i = j - 1;
    }
    if(!success) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

叠罗汉问题（奶牛垂直堆叠风险最小化）

题目描述

农民约翰的 (N) 头奶牛（编号为 (1\ldots N)）计划逃跑并加入马戏团，为此它们练习“叠罗汉”杂技：奶牛站在彼此的身上，形成一个高高的垂直堆叠。每头奶牛都有重量 (W_i) 和强壮程度 (S_i)。当奶牛 (i) 站在一系列奶牛上时，其风险值定义为其上方所有奶牛的总重量（不包括自己）减去它的强壮程度：

风险值越大，这头奶牛撑不住的可能性越高。请为这些奶牛找出一种排列顺序，使得所有奶牛的风险值中的最大值尽可能小。

输入格式

  • 第一行包含一个整数 (N)，表示奶牛数量。
  • 接下来 (N) 行，每行包含两个整数 (W_i) 和 (S_i)，分别表示第 (i) 头奶牛的重量和强壮程度。

输出格式

输出一个整数，表示在最优排列下，所有奶牛的最大风险值的最小可能值。

数据范围

  • $1 \le N \le 50000$
  • $1 \le W_i \le 10000$
  • $1 \le S_i \le 10^9$

输入样例

1
2
3
4
3
10 3
2 5
3 3

输出样例

1
2

解题思路

按照 $w + s$ 排序即可。

证明思路

考察相邻的两头牛 $i, i + 1$ 是否需要交换，它们的交换不影响其余牛的危险值。

交换前：$i: \sum^{i-1}{j = 1}w_j - s_i, i + 1: \sum^{i}{j=1}wj - s{i+1}$

交换后：$i: \sum^{i-1}{j=1}w_j + w{i+1} - si, i + 1: \sum^{i-1}{j=1}wj - s{i+1}$

比较交换后的 $i$ 与交换前的 $i + 1$即可。

此时假设：$\sum^{i-1}{j=1}w_j + w{i+1} - si \ge \sum^{i}{j=1}wj - s{i+1}$

即：$w{i+1} - s_i \ge w_i - s{i+1}$

即：$w{i+1} + s{i+1} \ge w_i + s_i$

即如果满足上式，则交换后的危险值会变大，意即 $w + s$ 大的应该排在后。

Code

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

struct e{
    int w, s;
    bool operator < (const e &x)const{
        return w + s < x.w + x.s;
    }
}cows[N];

int n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> cows[i].w >> cows[i].s;
    sort(cows + 1, cows + n + 1);
    int res = -2e9, weight = 0;
    for(int i = 1; i <= n; ++ i) {
        res = max(res, weight - cows[i].s);
        weight += cows[i].w;
    }
    cout << res << endl;
    return 0;
}