前言

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心问题的解法比较随缘，一般通过猜测加以验证，使局部最优等于全局最优。虽然听起来玄学……

区间问题

区间选点(与下题等价)

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

输出选择点的最小数量。

位于区间端点上的点也算作区间内。

输入格式

第一行包含整数N，表示区间数。

接下来N行，每行包含两个数量ai,bia_i,b_i，表示一个区间的两个端点

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

输出格式

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

1
2

数据范围

1≤N≤1051 \le N \le 10^5

−109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9

image-20220225153115401
  1. 所有区间按照右端点排序
  2. 枚举每一个区间，如果该区间还未选择点，则选取它的右端点

证明可行性：ans代表选的点的最小值（即答案），cnt代表按照上述方法选取的点的数量

如要证明ans=cntans=cnt，则需要先后证明ans≤cntans\le cnt和ans≥cntans \ge cnt

要使选取的点覆盖每一个区间，最坏的情况是每一个区间都有一个点，因此ans≥cntans \ge cnt

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

using namespace std;

const int N = 1e5 + 10;
int n;

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

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int a,b;
        scanf("%d%d", &a, &b);
        range[i] = {a, b};
    }
    
    sort(range, range+n);
    
    int res = 0, ed = -2e9;
    // 判断为新的区间时，更新区间范围
    for (int i = 0; i < n; i++) 
        if (ed < range[i].l) {
            res++;
            ed = range[i].r;
        }
        
    printf("%d\n", res);
    
    return 0;
}

最不相交区间的数量

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

输出可选取的最大的区间数量。

输入格式

第一行包含整数N，表示区间数。

接下来N行，每行包含两个数量ai,bia_i,b_i，表示一个区间的两个端点

输出格式

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

数据范围

1≤N≤1051 \le N \le 10^5

−109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9

cnt代表可行方案。ans代表可行方案中的最大值，也就是答案

  • ans≥cntans \ge cnt：cnt表示选出的符合条件的所有区间的个数，ans为其中的最大值，因此ans≥cntans \ge cnt

  • ans≤cntans \le cnt：反证法，假设ans>cntans > cnt，我们一共选出了cnt个符合条件的区间，意味着有cnt个点存在于区间中（区间选点）。在可以选出比cnt更多的ans个区间的情况下，只存在cnt个点，一个点代表一个区间，那么一定有两个或两个以上的区间有重合的部分，不符合题意，原式得证

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

using namespace std;

const int N = 1e5 + 10;

int n;

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

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        range[i] = {a, b};
    }
    
    sort(range, range+n);
    
    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ ) 
        if (ed < range[i].l) {
            res++;
            ed = range[i].r;
        }
    
    printf("%d", res);
    
    return 0;
}

区间分组(小根堆)

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

输入格式

第一行包含整数N，表示区间数。

接下来N行，每行包含两个数量ai,bia_i,b_i，表示一个区间的两个端点

输出格式

输出一个整数，表示最小组数

数据范围

1≤N≤1051 \le N \le 10^5

−109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9

  1. 将所有区间按照左端点从小到大排序(左端点递增)
  2. 从前往后处理每个区间，判断其能否放入到现有的组中L[i] > Max_R
    1. 若满足此条件，将其分给当前区间，并更新右端点
    2. 若不满足，则要新开一个分组，再将其加入

证明可行性：ans代表最终答案，cnt代表利用上述的算法得到的合法答案：

  • ans≤cntans \le cnt：cnt得到的一定是合法方案，ans为方案中的最小值，因此成立
  • ans≥cntans \ge cnt：cnt个区间都有至少一个公共点，所以要至少要分成cnt个组，所以最终答案ans>=cnt
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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

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

int n;

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    
    // 按左端点排序
    sort(range, range + n);
    
    // 小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    
    for (int i = 0; i < n; i ++ ) {
        auto r = range[i];
        // 新开一个组
        if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else {
            // 合入已有的组，并更新右端点
            int t = heap.top();
            heap.pop();
            heap.push(r.r);
        }
    }
    
    printf("%d\n", heap.size());
    
    return 0;
}

区间覆盖

给定NN个闭区间[ai,bi][a_i,b_i]以及一个线段区间[s,t][s,t]，请你选择尽量少的区间，将指定的线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出-1。

输入格式

第一行包括两个整数s和t，表示给定线段区间的两个端点。

第二行包含整数N，表示给定区间数。

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

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

输出格式

输出一个整数，表示所需最少区间数。

如果无解，则输出-1。

1
2

数据范围

1≤N≤1051 \le N \le 10^5

−109≤ai≤bi≤109-10^9 \le a_i \le b_i \le 10^9

−109≤s≤t≤109-10^9 \le s \le t \le 10^9

  1. 将区间按照左端点从小到大排序
  2. 从前往后依次枚举每个区间，在所有能覆盖start的区间当中，选择右端点最大的那个区间，并把start更新为这个区间的右端点值

证明可行性：ans代表最终答案，cnt代表利用上述的算法得到的合法答案：

  • ans≤cntans \le cnt：cnt得到的一定是合法方案，ans为方案中的最小值，因此成立
  • ans≥cntans \ge cnt：此算法得出的cnt为最优解，ans因此等于cnt
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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;

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

int main() {
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    
    sort(range, range + n); // 排序
    
    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ ) {
        int j = i, r = -2e9;
        
        // 找出每一轮区间包含st的最大右端点
        while (j < n && range[j].l <= st) {
            r = max(r, range[j].r);
            j++;
        }
        
        if (r < st) {
            res = -1;
            break;
        }
        
        res++;
        if (r >= ed) {
            success = true;
            break;
        }
        
        // i在for循环里，最后还要+1，所以如果i=j的话，相当于跳过了一个区间，所以只能i=j-1
        i = j - 1; 
        // 更新start至最大右端点
        st = r;
    }
    
    if (!success) res = -1;
    
    printf("%d\n", res);
    
    return 0;
}

Huffman树

构造方法：每次选择权值最小的两个点合并

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

image-20220228094316581

合并果子

有效性证明（两步均用到了贪心）：

  • 最小的两个点，深度一定最深，且可以互为兄弟。假设b>f，交换bf的值后

    (3f+2b)−(3b+2f)=3f+2b−3b−2f=f−b<0(3f+2b)-(3b+2f)=3f+2b-3b-2f=f-b<0，意味着交换后，总权值更小，因此深度一定最深

  • 依次将最小的两个点合并，这个过程合理并可以达到最优解

    f(n)=f(n−1)+a+bf(n)=f(n-1)+a+b，为最小值的点在每步同时减去一个数仍为最小值（转换化第一步）

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

using namespace std;

int n;

int main() {
    scanf("%d", &n);
    
    // 小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    
    for (int i = 0; i < n; i ++ ) {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }
    
    int res = 0;
    while(heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a+b);
    }
    
    printf("%d\n", res);
    
    return 0;
}

148.合并果子

排序不等式

排队打水

有nn个人排队到一个水龙头打水，第ii个人装满水的时间是tit_i，请问如何安排他们的打水顺序，才能使所有人的等待时间之和最小？

输入格式

第一行包含一个整数nn

第二行包含nn个整数，其中第ii个整数代表第ii个人装满水桶所花的时间tit_i

1
2
7
3 1 2 6 4 5 7

输出格式

输出一个整数，表示最小的等待时间之和

1
56

数据范围

1≤n≤1051 \le n \le 10^5

1≤ti≤1041 \le t_i \le 10^4

总时间=t1∗(n−1)+t2∗(n−2)+t3∗(n−3)+...总时间=t_1*(n-1)+t_2*(n-2)+t_3*(n-3)+...

将打水量从小到大排序，总时间最小。依次算前一位让后面等待的每一位的时间之和

反证法：不是按照从小到大排序，那么存在ti>ti+1t_i>t_{i+1}

原：ti∗(t−i)+ti+1∗(t−i−1)t_i*(t-i)+t_{i+1}*(t-i-1)

现：ti+1∗(t−i)+ti∗(t−i−1)t_{i+1}*(t-i)+t_i*(t-i-1)

两者相减，得ti−ti+1>0t_i-t_{i+1}>0。由此说明如果交换两者后，得到的总时间会更小，得证。

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
int n; 
int t[N];


int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);
    
    sort(t, t + n); // 1、排序
    
    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += t[i] * (n - i - 1); // 计算每一位
    
    printf("%lld\n", res);
    
    return 0;
}

绝对值不等式

货仓选址

x1,x2,x3,...x_1,x_2,x_3,...分别为数轴上的点，，假设选择xtx_t建点，那么距离之和为

f(x)=∣x1−xt∣+∣x2−xt∣+...+∣xn−xt∣f(x)=|x_1-x_t|+|x_2-x_t|+...+|x_n-x_t|

已知当只有两个点时，那么一定是建在两个点之间时，到两点的距离之和最小。

推广到多个点，则应该在所有点的中间时，即为货仓地址

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

using namespace std;

const int N = 1e5 + 10;
int n;
int x[N];

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &x[i]);
    
    sort(x, x + n);
    
    int res = 0;
    
    for (int i = 0; i < n; i ++ ) res += abs(x[i]-x[n/2]);
    
    printf("%d\n", res);
    
    return 0;
}

104.货仓选址

推公式

耍杂技的牛

贪心问题的编码比较简单，所以我们严格来说明一下它的推导，来回答为什么这样解是怎么想到的，以及它为什么正确。

根据题意，我们要求的就是找出一种牛的排列方式，令max(w1+⋅⋅⋅+wi−1−si)max(w_1+⋅⋅⋅+w_{i−1}−s_i)最小，记这个值为valval。

为了求排序的方案，到底是按重量排，还是按强壮程度排？

可以交换ii,i+1i+1牛的位置，看看满足什么等价条件，就可以使得交换之后valval更小。

因为只交换两个位置的牛，不会影响到其它位置，所以我们分别计算以下4种情况的valval，推导结果如下：

Val 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前 w1+w2+...+wi−1−siw1+w2+...+w_{i-1}-s_i w1+w2+...+wi−1+wi−si+1w1+w2+...+w_{i-1}+w_i-s_{i+1}
交换后 w1+w2+...+wi−1−si+1w1+w2+...+w_{i-1}-s_{i+1} w1+w2+...+wi−1+wi+1−siw1+w2+...+w_{i-1}+w_{i+1}-s_i

观察式子中发现都有w1+w2+...+wi−1w1+w2+...+w_{i-1}，于是将其减去，得

Val 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前 −si-s_i wi−si+1w_i-s_{i+1}
交换后 −si+1-s_{i+1} wi+1−siw_{i+1}-s_i

为方便比较，4个式子同时加上si+si+1si+s_{i+1}

Val 第ii个位置上的牛 第i+1i+1个位置上的牛
交换前 si+1s_{i+1} wi+siw_i+si
交换后 sis_i wi+1+si+1w_{i+1}+s_{i+1}

已知wi+si>siw_i+si > s_i，wi+si>wi+1+si+1w_i+si > w_{i+1}+s_{i+1}(假设现在是从大到小排序)，我们能够发现

当前一个位置上的wi+siw_i+si大于后一个位置时，交换后可以得到valval的最小值，即max(si+1,wi+si)≥max(si,wi+1+si+1)max(s_{i+1},w_i+s_i) \ge max(s_i, w_{i+1}+s_{i+1})

因此我们想到将奶牛按照w+sw+s从小到大排序，证毕。

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

using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10;

int n;
vector<PII> v;

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) {
        int w, s;
        scanf("%d%d", &w, &s);
        v.push_back({w+s,w});
    }
    
    sort(v.begin(), v.end());
    
    int sum = 0, res = -2e9;
    for (int i = 0; i < n; i ++ ) {
        int w = v[i].second, s = v[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    
    printf("%d\n", res);    
    return 0;
}

125.耍杂技的牛

参考资料

AcWing算法基础课, 报就完事！！！