《算法竞赛进阶指南》0x07 贪心

一只野生彩色铅笔

发布于 2022-10-31 10:59:17

7910

发布于 2022-10-31 10:59:17

贪心算法基础概念

From Wikipedia A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

贪心类问题无疑是基础算法中难度最大的，难点在于思维的跳跃性，没有固定的解题模式，往往是一类题一种解法或结论

贪心算法(Greedy Algorithm) 这样的称呼，往往让刚学习的朋友会误解这类题目的特性

Greedy Algorithm 实际上是在每个阶段做出 启发式（heuristic） 的 局部最优化选择，从而达到 全局最优化 的行为

heuristic 在数学最优化问题中的定义：a technique designed for solving a problem more quickly when classic methods are too slow or for finding an approximate solution when classic methods fail to find any exact solution 即在常规方法不能有效求解时，需要用到的启发式求解（这也就是为什么贪心问题特别杂，往往一题一结论，很难掌握）

如果用“状态空间”来理解的话，动态规划(Dynamic Programming) 在每个 stage 求解所有需要的状态实现递推

而 贪心算法(Greedy Algorithm) 则是在每个 stage 根据 启发式策略 策略只去求解部分解实现递推

从“集合”来理解的话，DP就是把每个状态集合都求干净进行递推；贪心则是每次求集合中的符合策略的一部分递推

贪心类型题目解法

之前也说过，贪心类题目没有固定解题模式，不像数据结构计算几何可以一步步推理得出，贪心解法具有跳跃性

使用贪心算法要求问题的整体最优性可以由局部最优性导出

因此，我们可以从局部最优策略下手，证明该策略也可以实现整体最优

常见的证明手段：

微扰（邻项交换）证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差常用于以 “排序” 为贪心策略的证明（减少逆序对不会使整体结果变差）
范围缩放证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差
决策包容性证明任意局面下，做出局部最优决策以后，在问题状态空间中的可达集合包含了做出其他任何决策后的可达集合换言之，这个局部最优策略提供的可能性包含其他有策略提供的可能性
反证法
数学归纳法

常见的贪心模型

区间问题
1. 区间选点
  1. 问题：数轴上选尽可能少的点，使得每个区间内至少有一个点
  2. 启发策略：区间按右端点排序，若当前区间包含当前的点，则不加入新点，否则更新新点为右端点
2. 最大不相交区间数量
  1. 问题：数轴上有若干区间，选出最大不相交区间
  2. 启发策略：与上一个问题等价，右端点排序，若当前区间与正在维护的区间相交，则不选，否则选上当前区间并维护
3. 区间分组
  1. 问题：数轴上有若干区间，给这些区间分组，使得每组内不相交
  2. 启发策略：区间按左端点排序，若当前所有组中最后一个加入的区间右端点都大于当前区间左端点，则开新组，否则接在最小的后面
4. 区间覆盖
  1. 问题：选择尽可能少的区间，覆盖一个线段
  2. 启发策略：区间按左端点排序，找出所有左端点在当前已覆盖的区间内，最远的右端点位置，更新已覆盖区间，继续枚举
Huffman 树模型
1. 问题：给出几个带权点，每次可以合并几个点，求最小带权路径长
2. 启发策略：每次选最小的几个点合并
排序不等式
1. 问题：小学奥数的排队打水问题
2. 启发策略：按照时间递增排序
绝对值不等式
1. 详情见“排序”章节
模拟退火
1. 问题：找多峰函数的极值
2. 启发策略：这个内容很多，以后章节会详细讲

习题

防晒

题目描述

有

头奶牛进行日光浴，第

头奶牛需要

minSPF[i]

到

maxSPF[i]

单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有

种，涂上第

种之后，身体接收到的阳光强度就会稳定为

SPF[i]

，第

种防晒霜有

cover[i]

瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式

第一行输入整数

和

接下来的

行，按次序每行输入一头牛的

minSPF

和

maxSPF

值，即第

行输入

minSPF[i]

和

maxSPF[i]

再接下来的

行，按次序每行输入一种防晒霜的

SPF

和

cover

值，即第

行输入

SPF[i]

和

cover[i]

每行的数据之间用空格隔开

输出格式

输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围

1≤C,L≤2500

1≤minSPF≤maxSPF≤1000

1≤SPF≤1000

输入样例：

输出样例：

解析

启发式策略：按照

maxSPF

右端点从小到大排序，然后枚举每头牛，每次选择区间内最小的防晒霜

证明方法有两种，蓝书上的范围缩放和y总的二分图反证不存在增广路径

我简略介绍一下两种证明方法，具体大家可以去参考这两位佬的详细证明过程

范围缩放

每瓶防晒霜是否可用，取决于

[minSPF[i], maxSPF[i]]

由于牛牛们按照

maxSPF

从小到大排好序了，因此每一个不高于当前奶牛

maxSPF

的防晒霜，都不会高于后续奶牛的

maxSPF

对于当前奶牛可用的任意两瓶防晒霜

和

，如果

SPF[x] < SPF[y]

那么后面其他奶牛与该两瓶防晒霜的关系有：

两瓶都能用
两瓶都不能用

不能用，

能用

因此，当前奶牛选择较小的

对于整体问题的影响显然比选择较大的

更好

另外，每头奶牛对答案的贡献至多为 1。即使放弃当前奶牛，留下防晒霜给后面的奶牛，对答案的贡献也不会变大

综上，得证该策略为正确策略

增广路径

将所有区间看做二分图的一个顶点集，将所有防晒霜的点看做另一个顶点集

证明对于当前牛选择该防晒霜的策略下，不存在一条增广路径即可

显然，增广路径的匹配是区间、点交替匹配的，以当前防晒霜的点为起点寻找增广路径（终点一定是未匹配的区间的顶点）

如果向后寻找增广路径，显然会使得路径变短，违背了定义
如果向前寻找增广路径，根据我们枚举的顺序，终点一定是已匹配的区间的顶点，违背了定义

因此不存在增广路径，所以该启发式策略一定是最优策略

cin >> n >> m;
spfs[1001] = n; //边界处理最大情况
for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
for (int i = 0, x, t; i < m; i ++ )
{
    cin >> x >> t;
    spfs[x] += t;
}
sort(seg, seg + n);
int res = 0;
for (int i = 0; i < n; i ++ )
{
    auto spf = spfs.lower_bound(seg[i].l);
    if (spf -> first <= seg[i].r)
    {
        res ++ ;
        if ( -- spf -> second == 0)
        {
            spfs.erase(spf);
        }
    }
}
cout << res << endl;

畜栏预定

题目描述

有

头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定

头牛和每头牛开始吃草的时间

以及结束吃草的时间

，每头牛在

[A,B]

这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第

行：输入一个整数

。

第

2..N+1

行：第

i+1

行输入第

头牛的开始吃草时间

以及结束吃草时间

，数之间用空格隔开。

输出格式

第

行：输入一个整数，代表所需最小畜栏数。

第

2..N+1

行：第

i+1

行输入第

头牛被安排到的畜栏编号，编号是从

开始的连续整数，只要方案合法即可。

数据范围

1≤N≤50000

1≤A,B≤1000000

输入样例：

输出样例：

解析

区间分组 的板子

启发式策略

区间按左端点升序枚举
如果之前存在一个组的区间右端点不与当前区间左端点相交，则将当前区间插入该组
如果之前 不存在 一个组的区间右端点不与当前区间左端点相交，则开一个新的分组存放当前区间

反证法，假设最优解的区间组数是

考虑在上述做法中，设第一次新建第

m+1

个组的时刻，是在处理第

个区间

由于所有区间是按左端点升序排序，所以现在前

个组中最后一个区间的左端点一定小于等于第

个区间的左端点

且前

个组中最小的右端点大于等于第

个区间的左端点，所以前

个组里最后一个区间一定都包含第

个区间的左端点，所以我们就找到了

m+1

个区间存在交集，所以至少需要

m+1

个畜栏，矛盾。

做法：用一个小根堆来维护所有组的右端点，以此来判断是否存在一个组的区间右端点不与当前区间左端点相交

sort(seg + 1, seg + n + 1);
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = 1; i <= n; i ++ )
{
    if (heap.empty() || heap.top().x >= seg[i].l)
    {
        res[seg[i].id] = heap.size() + 1;
        heap.push({seg[i].r, heap.size() + 1});
    }
    else
    {
        int t = heap.top().y;
        heap.pop();
        res[seg[i].id] = t;
        heap.push({seg[i].r, t});
    }
}

雷达设备

题目描述

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为

，当小岛与某雷达的距离不超过

时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为

轴，海的一侧在

轴上方，陆地一侧在

轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数

和 $d4，分别代表小岛数目和雷达检测范围。

接下来

行，每行输入两个整数，分别代表小岛的

，

轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1。

数据范围

1≤n≤1000

−1000≤x,y≤1000

输入样例：

输出样例：

解析

区间选点 板子

启发式策略：

区间按右端点升序排序
对于当前未选点的区间，以他的右端点作为我们选择的点
1. 之后所有左端点小于该点的区间都被该点覆盖
2. 对于第一个未被该点覆盖的区间，重复上述操作

证明：

按照上述做法，我们选择的点都是某个区间的右端点，而且由于区间按右端点排好序了，所以我们选择的点也是排好序的

只有在当前区间和上一个点所对应的区间是没有交集时，我们才会选择一个新点，所以所有选出的点所对应的区间两两之间没有交集

找到了

个两两之间没有交集的区间，因此我们至少需要选

个点，得证启发式策略为最优策略

int cnt = 0;
sort(seg + 1, seg + n + 1);
double pos = -1e9;
for (int i = 1; i <= n; i ++ )
{
    if (pos + eps < seg[i].l)
    {
        cnt ++ ;
        pos = seg[i].r;
    }
}

国王游戏

题目描述

恰逢

国国庆，国王邀请

位大臣来玩一个有奖游戏。

首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。

然后，让这

位大臣排成一排，国王站在队伍的最前面。

排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:

排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。

注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数

，表示大臣的人数。

第二行包含两个整数

和

，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来

行，每行包含两个整数

和

，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

数据范围

1≤n≤1000

0<a,b<10000

输入样例：

输出样例：

解析

不难发现，大臣的次序会影响枚举出来的，因此我们需要一种排序的启发式策略进行求解

因此选择 领项交换 来找出局部最优策略

考虑交换

与

i+1

位大臣的次序，则交换前，两人获得的奖赏为：

[ val_i = \frac{1}{R_i} \prod_{k=1}^{i-1}L[k] \quad ,val_{i+1} = \frac{1}{R_{i+1}} L_i \prod_{k=1}^{i-1}L[k] ]

交换后，两人获得的奖赏为：

[ val_{i+1}' = \frac{1}{R_i} \prod_{k=1}^{i-1}L[k] \quad ,val_i' = \frac{1}{R_{i+1}} L_{i+1} \prod_{k=1}^{i-1}L[k] ]

交换前，获得奖赏较多的大臣获得的奖赏为：

\prod\limits_{k=1}^{i-1}L[k] \times \max \Big( \dfrac{1}{R_i}, \dfrac{L_i}{R_{i+1}} \Big)

交换后，获得奖赏较多的大臣获得的奖赏为：

\prod\limits_{k=1}^{i-1}L[k] \times \max \Big( \dfrac{1}{R_{i+1}}, \dfrac{L_{i+1}}{R_{i}} \Big)

做差比较交换后式子，先通分再提出因式，有：

f = \max(R_{i+1}, R_{i}L_{i}) - \max(R_i, R_{i+1}L_{i+1})

我们的目的是使任意邻项发生交换时，获得奖赏不会增大，即若

小于等于

，则交换前才更优

由于

R_j, L_j

都是正整数，固有：

R_{j}L_{j} \ge R_j

若

R_iL_i < R_{i+1}L_{j+1}

，则：

R_{i+1} > R_iL_i

时，

f = R_{i+1} - \max(R_i, R_{i+1}L_{i+1}) \le 0

R_{i+1} < R_iL_i

时，

f = R_iL_i - \max(R_i, R_{i+1}L_{i+1}) \le 0

显然，交换前方案更小（优）

若

R_iL_i \ge R_{i+1}L_{j+1}

，则：

f = R_iL_i -(R_i, R_{i+1}L_{i+1}) 0

显然，交换后方案更小（优）

综上，排序方案为按

R_iL_i

升序排列

另外本题最坏情况的前缀积为

(10^3)^{10000} = 10^{30000}

需要上高精度

sort(seg + 1, seg + n + 1);
vector<int> prefix = {seg[0].l}, res;
for (int i = 1; i <= n; i ++ )
{
    vector<int> t = div(prefix, seg[i].r);
    if (lw(res, t)) res = t;
    prefix = mul(prefix, seg[i].l);
}
for (int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
cout << endl;

给树染色

题目描述

一颗树有

个节点，这些节点被标号为：

1,2,3…n

，每个节点

都有一个权值

A[i]

。

现在要把这棵树的节点全部染色，染色的规则是：

根节点

可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为

T×A[i]

，其中

代表当前是第几次染色。

求把这棵树染色的最小总代价。

输入格式

第一行包含两个整数

和

，分别代表树的节点数以及根节点的序号。

第二行包含

个整数，代表所有节点的权值，第

个数即为第

个节点的权值

A[i]

。

接下来

n−1

行，每行包含两个整数

和

，代表两个节点的序号，两节点满足关系：

节点是

节点的父节点。

除根节点外的其他

n−1

个节点的父节点和它们本身会在这

n−1

行中表示出来。

同一行内的数用空格隔开。

输出格式

输出一个整数，代表把这棵树染色的最小总代价。

数据范围

1≤n≤1000

1≤A[i]≤1000

输入样例：

输出样例：

解析

如果没有“先选父节点”的限制，每轮可以任意选择一个点染色，那么本题就是一个 排序不等式 的结论题

考虑加了这一限制后，如何处理本问题，易发现一个简单性质：

对含有最大权值的结点，对其父节点染色后，下一个染色对象必然是他（排序不等式易证）

既然该结点与他的父节点的染色顺序是相邻的，根据该性质，我们可以将这两个点合并成一个点，合并后的新结点权值，为两个点权值的平均值

例如有权值

x,y,z

的三个点，其中

x,y

染色是连续进行的，那么有两种染色方案：

后

x,y

，其代价为：

z + 2x + 3y

x,y

后

，其代价为：

x + 2y + 3z

做差易得：x + y - 2z ，若 $z < \dfrac{x+y}{2}$ 时，$z$ 先于 $x,y$；若 $z > \dfrac{x+y}{2}$ 时，$x,y$ 先于 $z$

因此，

x,y,z

三点的染色顺序可以转化为

\dfrac{x+y}{2}, z

两点的染色顺序

将上述简单情况推广到一般情况，假设有两组点

a_1,\cdots,a_n

和

b_1,\cdots,b_m

进行染色：

a_i

后

b_i

，其代价为：

\sum_{i=1}^n ia_i + \sum_{i=1}^m (i+n)b_i

b_i

后

a_i

，其代价为：

\sum_{i=1}^m ib_i + \sum_{i=1}^n (i+m)a_i

做差易得：

n\sum_{i=1}^mb_i-m\sum_{i=1}^na_i

，若

\dfrac{\sum_{i=1}^mb_i}{m} > \dfrac{\sum_{i=1}^na_i}{n}

，则

b_i

先于

a_i

；反之后于

由此得到一个 “等效权值” 的算法：记录每个点是由多少个点合并而成的，一个点的 “等效权值” 定义为：

[ \text{该点的等效权值} = \dfrac{\text{该点包含的原始权值总和}}{\text{该点包含的原始点数}} ]

最终做法是：不断在树中找到 “等效权值” 最大的点

，让其与其父节点

合并，并让

染色顺序接在

之后，直到树中只剩下一个点为止，合并完成。根据合并过程中的染色顺序，计算最终的代价

关于答案统计

我这里给出一个完全不同的思路，不用像y总那样推导出每次便宜后的总值，思维量会稍微小一点

不难发现 “等效权值” 点所代表的一类点可以看做一个集合，那么不妨用 带权并查集 来维护每个等效权值点

点权：在根节点维护这个集合的“等效权值”以及集合的大小
边权：用边权维护在这个集合中该节点的次序

这样最后整个树中只会有一个并查集，因此每个点到根的路径长，就是他在染色过程中的次序

int find(int u) //边权并查集
{
    if (p[u] != u)
    {
        int t = find(p[u]);
        d[u] += d[p[u]];
        p[u] = t;
    }
    return p[u];
}
void merge(int a, int b) // 注意顺序，要求是b作为父节点，a归到b下面，和一般并查集不一样
{
    p[a] = b;
    d[a] += siz[b];
    siz[b] += siz[a];
}
int get_maxid()
{
    double maxv = 0;
    int id = -1;
    for (int i = 1; i <= n; i ++ )
    {
        if (i != root && find(i) == i && v[i] > maxv)
        {
            id = i;
            maxv = v[i];
        }
    }
    return id;
}

int main()
{
    //读入和初始化
    cin >> n >> root;
    for (int i = 1; i <= n; i ++ )
        cin >> w[i], v[i] = w[i], d[i] = 0, p[i] = i, siz[i] = 1;
    
    for (int i = 1, a, b; i < n; i ++ )
        cin >> a >> b, fa[b] = a;
    
    for (int i = 1; i < n; i ++ )
    {
        int t = get_maxid(), father = find(fa[t]);
        v[father] = (v[t] * siz[t] + v[father] * siz[father]) / (siz[t] + siz[father]);;
        merge(t, father);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res += (d[i] + 1) * w[i];
    cout << res << endl;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-01-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度