0%

算法基础（17）

发表于 更新于 分类于 本文字数： 9.8k
第六章的内容：贪心（区间问题）

贪心问题的代码一般较简单，但证明其正确性较难，且没有常规的套路，更不用说常用的模板。（DP问题至少有常用的分析套路）。

1.区间问题

1.1.区间选点

例题：区间选点（Acwing 905）

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

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

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

数据范围：$1≤N≤10^5,−10^9≤a_i≤b_i≤10^9$

如下图的四个区间，所需的点的最小数量为2：

尝试用排序的思路做：

  1. 将每个区间按右端点有小到大排序

  2. 从前往后依次枚举每个区间（看区间右端点）：

    如果当前区间中已经包含点，则直接pass；

    否则，选择当前区间的右端点

每次都是选当前最好的情况（局部最优），走过去，贪心就是按照这种策略，最后可以走到最优解。

证明算法的正确性：每一个区间上都一定包含了一个点，当前选点的方案就是一组合法方案，包含的点数用cnt表示，本题的答案是所有可行方案中的最小值，用ans表示，则有ans <= cnt；考虑第2步的第二种情况，所有没被Pass的区间是什么情况：则需要cnt个相互之间没有交集的区间，若想把每个区间都覆盖掉，则至少需要cnt个点，则所有可行方案的点数都一定大于等于cnt，即ans >= 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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

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 l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    
    sort(range, range + n);   //按区间右端点从小到大排序
    
    int res = 0, ed = -2e9;   //res存点数，ed存上一次取的点
    for(int i = 0; i < n; i ++)
        if(range[i].l > ed)     //如果当前区间的左端点严格大于上一次取的点，则选择当前区间的右端点
        {
            res ++;
            ed = range[i].r;
        }
    
    printf("%d\n", res);
    
    return 0;
}

1.2.最大不相交区间的数量

例题：最大不相交区间的数量（Acwing 908）

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

数据范围：$1≤N≤10^5,−10^9≤a_i≤b_i≤10^9$

本题的做法和上题基本是一样的，证明方法也是类似的。（代码完全一样，就不写了）

为什么最大不相交区间数==最少覆盖区间点数呢？因为如果几个区间能被同一个点覆盖，说明它们相交了，所以有几个点就是有几个不相交区间。

1.3.区间分组

例题：区间分组（Acwing 906）

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

数据范围：$1≤N≤10^5,−10^9≤a_i≤b_i≤10^9$

区间贪心的问题基本都是先按照左/右端点从小到大排序。

本题的思路：

  1. 将所有区间按左端点从小到大排序；

  2. 从前往后处理每个区间：

    判断能否将其放到某个现有的组中，就是判断当前区间的左端点是否小于等于组中最大的右端点，L[i]<=Max_r，若小于等于则说明当前区间与组中区间有交集；若严格大于，则说明当前区间与组中区间没有交集，可放入组中。

    1）如果不存在这样的组，则开新组，然后再将其放进去；

    2）如果存在这样的组，将其放进去，并更新当前组的Max_r（随便挑一个放进去）

算法正确性的证明：

证明：1. Ans <= cnt； 2，Ans >= cnt，即证：Ans == cnt

这样选出来的方案一定是一种合法方案，每个组内的区间两两之间都没有交集，则有最小组数<=当前方案数，即Ans <= cnt；当在开第cnt个组时，说明当前区间与前cnt - 1个组都有交集，在这些组中都可以找到一个区间，使得当前区间的左端点Li在区间上（左端点小于Li，右端点大于Li），即这cnt个区间有一个公共点Li，因此不管怎么分，这cnt个区间中每一个区间都必须在一个单独的组中，因此所有可行方案中的区间数一定大于等于cnt，即Ans >= cnt，即证Ans = cnt。

对于当前区间如何判断是否存在一个组的Max_r > L[i]呢，可以把所有组的Max_r存入一个小根堆中（优先级队列），若其中最小的Max_r小于L[i]，则找到了满足条件的区间；若最小的Max_r都大于等于L[i]，则不存在这样的区间。

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<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l ,r;
    bool operator < (const Range & w) const
    {
        return l < w.l;
    }
}range[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    //否则，则说明存在一个组的Max_r小于当前区间左端点，当前区间可以放入该组中
        {
            //int t = heap.top();
            heap.pop();
            heap.push(r.r);
        }
    }
    
    printf("%d\n", heap.size());
    
    return 0;
}

1.4.区间覆盖

例题：区间覆盖（Acwing 907）

给定N个闭区间$[a_i,b_i]$以及一个线段区间$[s,t]$，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出-1。

输入格式：第一行包含两个整数s和t，表示给定线段区间的两个端点。第二行包含整数N，表示给定区间数。接下来N行，每行包含两个整数$a_i,b_i$，表示一个区间的两个端点。

输出格式：输出一个整数，表示所需最少区间数。如果无解，则输出-1。

数据范围：$1≤N≤10^5,−10^9≤a_i≤b_i≤10^9,−10^9≤s≤t≤10^9$。

本题的思路是：

  1. 将所有区间按左端点从小到大排序；
  2. 从前往后依次枚举每个区间，在所有能覆盖线段开始的位置start的区间当中，选择右端点最大的区间，然后将start更新成这个右端点的最大值。

证明算法的正确性：

本题可以直接证明相等，如下图分别是最小区间数，和用上面算法选出来的区间，对于最优解一定可以替换为算法得出来的解，即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
63
64
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

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 flag = false;
    for(int i = 0; i < n; i ++)
    {
        int j = i, r = -2e9;
        while(j < n && range[j].l <= st)  //双指针，找到能覆盖start（即左端点小于start）的所有区间的右端点的最大值
        {
            r = max(r, range[j].r);
            j ++;
        }
        
        if(r < st)   //如果找到的r小于线段的左端点，说明没有能覆盖线段的区间方案
        {
            res = -1;
            break;
        }
        
        res ++;
        if(r >= ed)  //如果找到的r大于等于线段的右端点，说明已经找到了方案，跳出循环
        {
            flag = true;   //有可能循环结束了还没有覆盖完线段，所有要找个标志来判断是否已经找到方案
            break;
        }
            
        st = r;
        i = j - 1;
    }
    
    if(!flag)  res = -1;
    printf("%d\n", res);
    
    return 0;
}

2.Huffman树

例题：合并果子（Acwing 148）

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以达达总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入格式：输入包括两行，第一行是一个整数$n$，表示果子的种类数。第二行包含$n$个整数，用空格分隔，第$i$个整数$a_i$是第$i$种果子的数目。

输出格式：输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于$2^31$。

数据范围：$1≤n≤10000,1≤a_i≤20000$

Huffman树是一颗完全二叉树，如下图，叶子结点是所有要合并的点，合并的代价是$3a+3b+3c+3d+2e+2f$，我们要在这一点的完全二叉树中选择出合并代价最小的一棵，并输出最小的代价。

做法：每次都是挑选最小的两堆合并（寻找局部最优），即每一步都贪心地选择局部最优解，就可以得到最优解。

注意本题与合并石子的区别：本题可以合并任意两堆果子，而合并石子只能合并相邻的两堆石子

证明：

  1. 最优解中，权值最小的两个点，一定在树中深度最深，且可以互为兄弟；（也可以这样理解：因为深度最深的点要计算最多次，所以在其位置用权值最小的点才会比较好）
  2. 贪心式的合并能否得到最优解，n-1堆合并的最优解不一定是n堆合并的最优解，如下图一次合并a和b，之后合并剩下n-1个点的某个方案的代价设为f(n-1)，则相应的合并n个点的方案的代价为f(n) = f(n-1) + a + b，我们的目标是求出f(n)的最小值，这些方案的第一步都是合并a和b，这样问题就转化为求f(n-1)的最小值，即转化为n-1个点的Huffman问题，则可以继续找权值最小的两个点合并。

每次求权值最小的两个点，可以用优先级队列的小根堆。

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<queue>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    
    priority_queue<int, vector<int>, greater<int>> heap;  //小根堆
    
    while(n --)
    {
        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;
}

3.排序不等式

例题：排队打水（Acwing 913）

有 n 个人排队到 1 个水龙头处打水，第$ i $个人装满水桶所需的时间是$ t_i$，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式：第一行包含整数 n。第二行包含 n 个整数，其中第$ i $个整数表示第$ i $个人装满水桶所花费的时间$ t_i$。

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

数据范围：$1≤n≤10^5,1≤t_i≤10^4$。

如打水顺序是：$3,6,1,4,2,5,7$，则等待的总时间就等于$36+65+14+43+22+51=73$。若打水顺序是：$t_1,t_2,t_3,\dots,t_n$，则总的等待时间是$t_1(n-1)+t_2(n-2)+t_3(n-3)+\dots+t_{n-1}1$。

直觉的做法是让打水时间长的人尽量靠后，让打水时间短的人靠前，即让所有人按打水时间从小到大排队，则总的等待时间是最小的。

如何证明：反证法，如果最优解不是按照从小到大排好序的，那一定有两个相邻的人有$t_i>t_{i+1}$，让这两人位置交换。交换前等待总时间中两项对应的时间为$t_i(n-i)+t_{i+1}(n-i-1)$，交换后为$t_{i+1}(n-i)+t_i(n-i-1)$，则后$-$前$=(n-i)(t_{i+1}-t_i)+(n-i-1)(t_i-t_{i+1})=t_{i+1}-t_i<0$，则说明交换后的总等待时间比当前小，则当前解不是最优解，因此可证按打水时间从小到大排序得到的是最优解。

贪心问题的证明方法一般从反证法；“夹逼”：由ans <= cnt，ans >= 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
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

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);
    
    long long res = 0;
    for(int i = 0; i < n; i ++)  res += t[i] * (n - i - 1);
    
    printf("%lld\n", res);
    
    return 0;
}

4.绝对值不等式

例题：货仓选址（Acwing 104）

在一条数轴上有 N 家商店，它们的坐标分别为$ A_1~A_N$。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式：第一行输入整数N。第二行N个整数$A_1~A_N$。

输出格式：输出一个整数，表示距离之和的最小值。

数据范围：$1≤N≤100000$

将数轴上商店的地址记为$x_1,x_2,x_3,\dots,x_n$，将仓库的地址记为$x$，则仓库到每家商店的距离之和为：$f(x)=|x_1-x|+|x_2-x|+|x_3-x|+\dots|x_n-x|$。

直接的做法是将仓库放在中位数的位置，若商店有奇数个，仓库就放在中位数；若商店有偶数个，仓库就放在两个中位数的中间任意位置（包括端点）。

求$f(x)$的最值，将数分成两组：

单看每一个括号中值，即求$|a-x|+|b-x|$的最小值，当$x\in [a,b]$时，取得最小值$b-a$，所以有$f(x)\ge x_n-x_1+x_{n-1}-x_2+\dots$，那等号能不能取到呢，即看等号对于每个括号内的项能不能同时取到，则$x$只要取到中位数（奇数个商店），或中间的两个数（偶数个商店）之间，上式就能取到等号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int n;
int a[N];

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

5.推公式

例题：耍杂技的牛（Acwing 125）

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。奶牛们不是非常有创意，只提出了一个杂技表演：叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量$W_i$以及自己的强壮程度$S_i$。一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式：第一行输入整数N，表示奶牛数量。接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第$i$行表示第$i$头牛的重量$W_i$以及它的强壮程度$S_i$。

输出格式：输出一个整数，表示最大风险值的最小可能值。

数据范围：$1≤N≤50000,1≤W_i≤10,000,1≤S_i≤1,000,000,000$

每个牛的危险系数等于它上面牛的重量之和减去它自己的强壮程度。

本题的做法是：按照$W_i+S_i$从小到大的顺序排序（从上到下，上面的牛最小），最大的危险系数一定是最小的。

证明：

  1. 贪心得到的答案 >= 最优解（显然）
  2. 贪心得到的答案 <= 最优解：若叠牛罗汉的最优解不是按照$w_i+s_i$从小到大排序的，那么必存在一个逆序对，使$w_i+s_i > w_{i+1}+s_{i+1}$，将第$i$个位置的牛和第$i+1$位置的牛交换，交换前后的危险系数对比为：
第$i$个位置上的牛的危险系数 第$i+1$个位置上的牛的危险系数
交换前 $w_1+w_2+\dots+w_{i-1}-s_i$ $w_1+w_2+\dots+w_{i}-s_{i+1}$
交换后 $w_1+w_2+\dots+w_{i-1}-s_{i+1}$ $w_1+w_2+\dots+w_{i-1}+w_{i+1}-s_i$

将上面各式都减去一个$w_i+w_2+\dots+w_{i-1}$，再加上一个$s_i+s_{i+1}$，就会变成：

第$i$个位置上的牛的危险系数 第$i+1$个位置上的牛的危险系数
交换前 $s_{i+1}$ $w_i+s_i$
交换后 $s_i$ $w_{i+1}+s_{i+1}$

因为上式各项都是$\ge 1$的，所以$w_i+s_i>s_i$，又有$w_i+s_i > w_{i+1}+s_{i+1}$，所以有$\max(s_i, w_{i+1}+s_{i+1})<w_i+s_i$，即有$\max(s_i, w_{i+1}+s_{i+1})< \max(s_{i+1}, w_i+s_i)$。则逆序对交换顺序后，两个位置上危险系数的最大值一定比交换前小，那么整体的危险系数的最大值一定小于等于交换前的，若把所有的逆序对都变成顺序，即用贪心得到的答案，那它的危险系数的最大值一定是小于等于最优解的（即交换前的）。

综上，就证明了贪心得到的答案就是最优解。

贪心问题可以先推出问题的公式（？），再运用一些数学中的不等式来解题。

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<algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 50010;

int n;
PII cow[N];

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