第八章:贪心与简单构造

有些问题要求从许多方案中找到最优解,有些问题只要求给出任意一个满足限制的方案。贪心用于前一类问题:每一步固定一个当前选择,并证明至少存在一个最优解包含这个选择。构造用于后一类问题:根据限制直接生成答案,再逐项验证答案始终合法。
本章先通过区间调度完整经历一次“发现规则、寻找反例、证明规则、实现算法”的过程,再把交换论证用于排队问题,并介绍从左向右固定前缀的另一类贪心。最后单独讨论构造,避免把“最优性证明”和“合法性验证”混在一起。
阅读前需要掌握数组、排序、结构体和时间复杂度。本章的四段实现均为独立的 C++17 程序;构造任务使用本章规定的输入输出,其余三段对应链接中的例题。
1. 从区间调度认识贪心
1.1 先确定当前选择解决了什么
例题:线段覆盖。
题意概述:给定 个活动,第 个活动占用半开区间 。同一时刻只能参加一个活动,求最多能够完整参加多少个活动。
数据范围为 ,。
枚举所有活动子集,再检查其中的区间是否互不重叠,需要处理指数级数量的候选。为了减少候选,可以先考虑答案中的第一个活动。
第一个活动结束得越早,后面可使用的时间范围越大。因此可以尝试下面的规则:
- 按结束时间从早到晚排列所有活动;
- 选择当前能够参加且结束最早的活动;
- 删除与它冲突的活动,对剩余活动重复同样的过程。
例如有以下活动:
| 活动 | 占用区间 |
|---|---|
按结束时间扫描时,先选择 。 和 与 冲突,不能再选; 的开始时间不早于 的结束时间,可以选择;随后 可以接在 后面。最终得到 ,共 个活动。
这个过程只说明了算法怎样运行,还没有说明它一定得到最优答案。贪心规则必须经过证明,不能只依据“留下的时间看起来更多”。
1.2 用交换论证固定第一个活动
设 是所有活动中结束最早的一个。任取一个最优方案,设其中第一个活动为 。
因为 的结束时间最早,所以
把最优方案中的 换成 。原来排在 后面的活动都在 时刻之后开始,也就一定不早于 开始。因此替换后仍然没有区间冲突,活动数量也没有减少。
这说明:即使原来的最优方案没有选择 ,也能把它改造成一个选择 的最优方案。于是可以放心固定 ,只处理在 结束后开始的活动。
固定第一个活动后,剩余任务仍然是“从一组活动中选择最多的互不重叠区间”,问题结构没有改变。相同论证可以不断重复,直到没有活动可选。
证明得到的结论不是“所有最优方案都以 开头”,而是“至少存在一个最优方案以 开头”。这已经足以支持贪心选择。
1.3 把选择规则写成排序与扫描
排序后,每次遇到能接在已选活动之后的区间就选择它。输入第一行给出 ,后面每行给出一个活动的开始、结束时间。结构体 保存活动的左右端点,比较函数按右端点升序排列;右端点相同时,左右端点的先后不会影响最多活动数,这里再按左端点升序保证顺序确定。
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+10;
struct node{
int l,r;
}a[N];
bool cmp(node x,node y){
if(x.r!=y.r)return x.r<y.r;
return x.l<y.l;
}
int main(){
int n,ans=0,last=0;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
if(a[i].l>=last){
ans++;
last=a[i].r;
}
}
printf("%d\n",ans);
}
变量 表示已选活动的结束时间。全部开始时间非负,所以初始值 不会排除任何活动;如果任务允许负时间,不能照抄这个初始值,需要另设“尚未选择”的标记。变量 是已选活动数。
这里使用半开区间 ,所以一个活动在时刻 结束,另一个活动可以恰好在时刻 开始,判断条件为 。若题目规定端点相接也算冲突,判断条件应改为严格大于。
排序需要 时间,扫描需要 时间,因此总时间复杂度为 ;保存全部活动需要 空间。
1.4 用反例排除错误规则
“按开始时间最早选择”不正确。例如活动为 、、 时,选择开始最早的 只能参加 个活动,而后两个短活动可以连续参加。
“按区间长度最短选择”也不正确。例如活动为 、、 时,中间区间长度最短,却同时与另外两个区间冲突;选择两侧区间可以参加 个活动。
反例还能帮助确定结论的适用范围。本节目标是最大化活动数量;如果每个活动还有不同收益,结束最早的活动未必属于最优方案,必须重新分析选择规则。
2. 从案例中提炼贪心证明
2.1 局部规则只是候选策略
贪心算法通常具有以下过程:当前做出一个选择,不再撤销,然后继续处理剩余问题。真正需要证明的是,这个不可撤销的选择不会排除所有最优方案。
“每次选最大”“每次选最小”都只是一条候选规则。例如,用面值 的硬币凑出金额 时,每次选择不超过剩余金额的最大面值,会得到 ,共使用 枚硬币;最优方案是 ,只使用 枚。局部数值最大不等于整体答案最优。
设计规则后,可以先检查以下小数据:
- 只有一个或两个对象;
- 多个关键字相等;
- 两种候选规则给出不同选择;
- 局部最优选择会占用稀缺资源;
- 题目限制恰好取到边界值。
小规模搜索也可以把贪心答案与暴力最优答案对比,用于发现反例。但有限数据只能否定错误规则,不能代替对全部输入的证明。
2.2 交换论证的四个步骤
区间调度的证明可以抽象成四步:
- 任取一个最优解;
- 若它没有采用当前的贪心选择,找到需要替换的对象;
- 把贪心选择换入最优解;
- 证明交换后仍然合法,并且目标值没有变差。
交换后得到的方案仍是最优方案,而且包含当前贪心选择。接下来还要检查:固定这个选择后,剩余问题是否仍与原问题具有相同结构。只有这一点成立,才能对后续选择重复同样的论证。
交换论证必须同时检查合法性和目标值。只说明“两个方案数量相同”,却没有说明替换后是否违反限制,证明并不完整。
2.3 不同问题需要不同证明方式
交换论证并不是贪心的唯一证明方法。常见思路还包括:
- 相邻交换:证明任何逆序都能交换成正确顺序,且答案不变差;
- 下界匹配:证明任何方案至少要付出某个代价,而算法恰好只付出这些代价;
- 固定前缀:处理完第 个对象后,证明当前前缀已经最优,并且不会再被后续操作修改。
后面的排队接水使用相邻交换,小 A 的糖果则同时使用不可避免的删除量和固定前缀。证明方式取决于选择规则产生的结构,不能看到排序或单向扫描就直接认定它是正确的贪心。
3. 相邻交换:排队接水
例题:排队接水。
题意概述:有 个人排队使用同一个服务窗口,第 个人需要 单位时间。一个人的等待时间不包括自己的服务时间。安排队伍顺序,使平均等待时间最小;若两个人用时相同,编号较小者排在前面。
数据范围为 ,。
平均等待时间等于总等待时间除以人数,而人数固定,因此只需最小化总等待时间。枚举所有排列需要检查阶乘级数量的方案,无法处理本题范围。
3.1 从两个人的先后顺序推出排序规则
设队伍中相邻两人的服务时间分别为 ,在他们之前已经累计了 单位服务时间。
若先安排 ,再安排 ,这两人的等待时间之和为
若交换顺序,先安排 ,再安排 ,等待时间之和为
排在这两人之后的顾客都需要等待 ,不会受到两人内部顺序的影响。因此,当 时,把服务时间较短的人放在前面不会使总等待时间增加。
若一个队伍中存在相邻逆序,即前一人的服务时间大于后一人,就可以交换这两人并减小总等待时间。不断消除逆序后,服务时间从小到大排列,所以升序方案最优。
例如服务时间为 时,原顺序的总等待时间为 ;升序排列为 后,总等待时间为 。
3.2 实现排序与等待时间累加
结构体同时保存服务时间与原编号。服务时间相同时按编号升序排列,这个并列规则不改变最小等待时间,但能满足题目的输出要求。
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
struct node{
int id,t;
}a[N];
bool cmp(node x,node y){
if(x.t!=y.t)return x.t<y.t;
return x.id<y.id;
}
int main(){
int n;
long long sum=0,ans=0;
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i].t;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
cout<<a[i].id<<(i==n?'\n':' ');
ans+=sum;
sum+=a[i].t;
}
printf("%.2f\n",1.0*ans/n);
}
扫描到第 个人之前, 保存前 个人的服务时间之和,也就是第 个人的等待时间。因此必须先把 加入总等待时间 ,再累加当前人的服务时间。第一行输入人数,第二行输入各人的服务时间;输出两行,分别为编号顺序与平均等待时间。
总等待时间最大可达到约 ,应使用 。排序需要 时间,扫描需要 时间,保存队伍需要 空间。
相邻交换推出的排序规则依赖于目标函数。若每个人的等待代价不同,交换前后的差值会发生变化,不能直接继续按服务时间排序。
4. 固定前缀:小 A 的糖果
例题:小 A 的糖果。
题意概述:有 个糖果盒,第 个盒子中有 颗糖。每次可以从任意一个盒子中吃掉一颗糖。求至少需要吃掉多少颗糖,才能使任意两个相邻盒子的糖果数之和都不超过 。
数据范围为 ,。
相邻限制只连接连续两个盒子,适合从左向右固定已经处理好的前缀。不过,在决定从哪一个盒子删糖前,需要先处理单盒上界。
4.1 先删除必然无法保留的糖果
任意盒子都与至少一个盒子相邻,糖果数又不会为负。如果最终满足相邻两盒之和不超过 ,每个盒子本身也一定不超过 。因此,盒子中超过 的部分无论如何都必须删除,可以先统一删去。
完成这一步后,每个盒子都有 。从左向右检查相邻两盒时,若
设超出量为
任何合法方案都必须从这两个盒子中合计删除至少 颗糖。因为 ,所以 ,可以把这 颗全部从右侧的第 个盒子删除。
这样既用最少的删除量修复了当前相邻对,又减小了下一对中的左侧盒子,不会给后续制造额外困难。已经处理过的左侧相邻关系不会再改变。
例如 、。第一对超出 ,从第二盒删除 颗,序列变为 ;第二对超出 ,从第三盒删除 颗,得到 。总共删除 颗。
4.2 实现与前缀不变量
以下数组使用 ,这样相邻和与总删除量都不需要额外转换类型。
#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
long long a[N];
int main(){
int n;
long long x,ans=0;
scanf("%d%lld",&n,&x);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
if(a[i]>x){
ans+=a[i]-x;
a[i]=x;
}
}
for(int i=2;i<=n;++i){
long long d=max(0LL,a[i-1]+a[i]-x);
a[i]-=d;
ans+=d;
}
printf("%lld\n",ans);
}
第二个循环处理完位置 后,前 个盒子中的所有相邻限制都已满足,后续操作只会修改位置 及其右侧,不会破坏这个前缀。
不过,“当前这对至少要删 颗”还不能直接累加成全局下界,因为中间盒子属于两对限制,同一次删除可能同时修复两对。需要证明把删除放到右侧不会错过更好的安排。
换成等价目标:最大化最后保留的糖果总数。记算法的结果为 ,截断后的原盒数为 。算法让 ,之后取 ,即在前一盒固定后,尽量多保留当前盒。
任取一个最优保留方案 。从左往右调整,假定 已经与算法相同。由单盒上界和左侧相邻限制,有 。令 ,把第 盒增加到 :左侧限制仍合法,因为 就是在这个限制内取到的值。
右侧可能超出。若 ,只需从第 盒减少 颗。原方案满足 ,所以 ;又因为 ,有 ,不会减成负数。第 盒增加 ,下一盒最多减少 ,保留总量不会下降;下一盒减少也不会破坏再往右的限制。当 时,已经没有右侧限制需要修复。
因此总能把一个最优方案逐盒改成算法的结果,且不损失保留量。算法保留量最大,也就删除量最小。这同时解释了为什么修复当前相邻对时优先删除右盒:左侧前缀可以固定,下一对还能从这次删除中受益。
例如 、,若第一对从左盒删除 ,得到 ,第二对还要删 ,总共删 ;从右盒删则只需删 。并不是任意一侧都一样好。
两个循环都只扫描数组一次,时间复杂度为 ,保存数组需要 空间。总删除量可能达到 ,答案必须使用 。
5. 简单构造:按奇偶性分组
考虑下面的任务:重新排列 至 ,使任意两个相邻数之差的绝对值都大于 。输出任意一种方案;无法做到时报告无解。数据范围为 。
这道题不要求比较多个合法方案的优劣,只要生成一个满足限制的排列即可。证明目标也随之改变:不需要证明“当前选择属于某个最优解”,而要证明输出没有遗漏、没有重复,并且每一处相邻关系都合法。
5.1 从禁止条件寻找稳定模式
限制只禁止差为 的数相邻。两个不同的偶数之差至少为 ,两个不同的奇数之差也至少为 。因此可以先升序输出全部偶数,再升序输出全部奇数。
这个方案包含三类需要检查的位置:
- 偶数组内部:相邻两数之差为 ;
- 奇数组内部:相邻两数之差为 ;
- 两组交界:当 时,最后一个偶数至少为 ,第一个奇数为 ,差至少为 。
例如 时,可以输出
当 时,没有相邻位置,直接输出 。当 或 时,数字 与其他所有可选数字的差都为 ,无法把它放入一个合法排列,所以无解。
先列出小规模,避免把大规模模式套到全部输入:
| 结果 | 检查 | |
|---|---|---|
| 没有相邻对 | ||
| 无解 | 唯一一对差为 | |
| 无解 | 无法与任何数相邻 | |
| 三处差为 | ||
| 多出的末项仍在奇数组内部 |
5.2 生成并输出方案
输入一个整数 ,输出一行排列;无解时输出 NO。
#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int a[N];
int main(){
int n,cnt=0;
cin>>n;
if(n==1){puts("1");return 0;}
if(n<=3){puts("NO");return 0;}
for(int i=2;i<=n;i+=2)a[++cnt]=i;
for(int i=1;i<=n;i+=2)a[++cnt]=i;
for(int i=1;i<=n;++i)cout<<a[i]<<(i==n?'\n':' ');
}
数组 保存要输出的排列, 是已经加入的元素数。两个循环分别加入所有偶数和所有奇数,每个 至 的整数恰好出现一次。生成与输出都需要 时间,数组需要 空间;若直接分两段输出,额外空间可以降为 。
构造中常见的奇偶分组、按余数分类、两类元素交替和短周期重复都只是候选模式。使用一种模式时,需要分别检查组内、组间交界、小规模无解情况,以及末尾不足一个完整周期时的情况。
6. 贪心与构造的区别
| 比较项 | 贪心 | 构造 |
|---|---|---|
| 任务目标 | 在合法方案中求最优值 | 输出任意一个合法方案 |
| 核心问题 | 为什么当前选择不会排除所有最优解 | 为什么输出覆盖全部限制 |
| 常见证明 | 交换论证、相邻交换、下界匹配、固定前缀 | 分类验证、模式验证、边界与无解证明 |
| 常见实现 | 排序、扫描、双指针、堆 | 分组、交替、分块、按周期生成 |
| 失败信号 | 能构造出局部选择更好、整体答案更差的反例 | 出现重复、遗漏、非法交界或未覆盖的小规模 |
排序、双指针和堆只是实现选择顺序的工具,不会自动保证贪心正确;同样,一个构造在若干样例上成立,也不能代替对所有位置和全部规模的验证。
7. 本章小结
- 贪心规则必须说明当前选择、剩余问题和最优性依据。
- 交换论证通过改造一个最优解,证明至少存在一个最优解采用当前选择。
- 相邻交换适合从两个对象的先后贡献中推导排序关键字。
- 从左向右扫描时,可以用前缀不变量说明已处理部分不会被后续操作破坏。
- 反例用于排除错误规则和确定适用范围,有限测试不能代替证明。
- 构造不要求最优,但必须验证元素完整性、全部约束、组间交界和小规模情况。
8. 作业
巩固练习
《纪念品分组》可以先用首尾双指针实现,再补充证明:每轮为什么可以固定当前最贵物品的安排,以及允许每组三件物品后原论证为何失效。
提高训练
完成练习时,应分别写出贪心选择、正确性依据、复杂度和失效条件;构造题还应单独检查无解规模与所有交界位置。
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…