贪心算法
贪心与其说是一种算法,不如说一种思想。
贪心思想,顾名思义,就是总是做出当前最好的选择,这种方式可能在全局上不是最好的结果,但是在一些题目中就可以直接用。
最简单的例子就是“货比三家”,在生活中,我们买东西时都会挑性价比最优的,这就是一种贪心。
贪心算法在OI中经常与其他算法或数据结构结合到一起,有些题目比较考验思维能力。
贪心算法一般会用到的算法或数据结构不多,一般的题目只需要用到排序,有些题目可以用优先队列动态维护最值。
接下来我们介绍几种贪心算法的“套路”。
取最优
最经典的问题就是最优装载问题。
商店里有$n$个物品,每个物品给出价值和重量,现在来了个小偷,小偷只能带走$m$千克的物品,问他最多能带走多少钱的物品。
对于这道题,我们可以直接算出每一个物品的性价比,然后对于性价比排序,依次累加,直到重量超过$m$为止。
代码
struct node{
int w,m;//价值和重量
double d;//性价比
}a[N];
bool cmp(node a,node b){
return a.d>b.d;//按照性价比从小到大排序
}
int n,m;
int main(){
cin>>n>>m;//n个物品,限定m重量
for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].m,a[i].d=(double)a[i].w/(double)a[i].m;
sort(a+1,a+1+n,cmp);//排序
int s1=0,s2=0;//分别为价值的累计和重量的累计
for(int i=1;i<=n;i++){
s1+=a[i].w,s2+=a[i].m;
if(s2+a[i+1].m>m) break;//如果超出m限制,就退出
}
cout<<s1;//输出累计价格
}
不相交区间问题
在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少?
关于这题的贪心策略,我们可以按每个区间的右端点排序,然后每个区间判断一下是否与前面的区间重合,累加答案即可。
代码
struct node{
int l,r;//结构体
};
vector<node>v;
int n,ans=0;
bool cmp(node a,node b){
return a.r<b.r;//按右端点排序
}
int main(){
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
v.push_back({l,r});//使用vector容器
}
sort(v.begin(),v.end(),cmp);
int l=v.front().l;//初始l为第一个区间的左端点
for(auto it:v){
if(it.l>=l){//如果不重合,就累加答案
ans++;
l=it.r;//更新l指针
}
}
cout<<ans;
}
区间选点问题
给定$N$个区间$[a,b]$,取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以重复)。
如何能选取更少的点呢?
如果在几个区间的重叠部分放点,那么就会覆盖多个区间,就会少取一些点。
如图,如果两个区间有重叠部分,那么前面区间的右端点肯定在重叠部分里。
所以我们可以选择在每个区间的右端点放点,这样就会覆盖更少的区间。
所以我们的贪心策略就是:首先按区间的结束位置从小到大排序。然后从区间$1$到区间$n$进行选择;对于当前区间,若集合中的数不能覆盖它,则将区间末尾的数加入集合。
代码
int vis[N];
struct node{
int u,v,w;
}a[N];
int m,h,ans=0;
int cmp(node a,node b){
return a.v<b.v;//按照右端点排序
}
int main(){
cin>>m>>h;
for(int i=1;i<=h;i++) cin>>a[i].u>>a[i].v>>a[i].w;
sort(a+1,a+1+h,cmp);//排序
for(int i=1;i<=h;i++){
int cnt=0;
for(int j=a[i].u;j<=a[i].v;j++) cnt+=vis[j];
if(cnt>=a[i].w) continue;
for(int j=a[i].v;j>=a[i].u,cnt<a[i].w;j--){
if(!vis[j]) cnt++,vis[j]++,ans++;
}
}
cout<<ans;
}
中位数
在贪心算法中,中位数是一个比较神奇的性质。
我们以经典的货仓选址问题为例。
在一条数轴上有 $N$ 家商店,它们的坐标分别为 $A_1∼A_N$。现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
可以证明,当选取中位数时,距离之和最小。
代码
int a[N],sum,n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int mid=a[n/2];
for(int i=1;i<=n;i++) sum+=abs(a[i]-mid);
cout<<sum<<endl;
}
与优先队列相结合
很多贪心题目可以和堆结合到一起,在平时做题时,可以使用stl中的优先队列priority_queue
。
合并果子是一道比较经典的优先队列优化贪心题。
有$n$个果子,每次可以任意选择两个进行合并,每次合并耗费的体力值是两个果子重量之和,问最小耗费体力值。
因为是任意两个进行合并,所以我们可以每次选择果子里面重量最小的两个果子合并。
但是暴力找重量最小的果子复杂度为$O(n)$,总体$O(n^2)$的时间复杂度不能接受。考虑用数据结构优化。
什么数据结构能支持动态找最小值呢?堆!
在这里我们可以使用stl中的优先队列,这样就有了$O(n\log n)$的复杂度。
代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;//优先队列
int n,ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int t;
cin>>t;
q.push(t);//在优先队列中加入所有果子
}
while(!q.empty()){
int t1=q.top();//取出当前重量最小的果子
q.pop();
if(q.empty()) break;
int t2=q.top();
q.pop();
ans+=t1+t2,q.push(t1+t2);
}
cout<<ans;
}
反悔贪心
没人看的,所以咕了
例题
一本通提高篇的几道贪心水题。
【一本通提高篇贪心】 活动安排
题目大意
选取最多的区间,使它们没有重叠部分。
贪心思路
按照活动的结束时间进行升序排序,因为一个活动结束的越早,就越不容易与其他活动起冲突。
这题就是上面写到的不相交区间问题,这里就不仔细讲了,直接看代码。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct node{
int l,r;//结构体
};
vector<node>v;
int n,ans=0;
bool cmp(node a,node b){
return a.r<b.r;//按右端点排序
}
int main(){
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
v.push_back({l,r});//使用vector容器
}
sort(v.begin(),v.end(),cmp);
int l=v.front().l;//初始l为第一个区间的左端点
for(auto it:v){
if(it.l>=l){//如果不重合,就累加答案
ans++;
l=it.r;//更新l指针
}
}
cout<<ans;
}
【一本通提高篇贪心】 种树
题目大意
即刚刚讲过的区间选点问题。
贪心思路
按每个路段的右端点排序,枚举每一个路段,从左端点枚举到右端点。
因为如果右端点重叠了,就少种了一棵树,所以只要这个位置有树,这个路段要求的树的数量就-1。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int vis[N];
struct node{
int u,v,w;
}a[N];
int m,h,ans=0;
int cmp(node a,node b){
return a.v<b.v;
}
int main(){
cin>>m>>h;
for(int i=1;i<=h;i++) cin>>a[i].u>>a[i].v>>a[i].w;
sort(a+1,a+1+h,cmp);
for(int i=1;i<=h;i++){
int cnt=0;
for(int j=a[i].u;j<=a[i].v;j++) cnt+=vis[j];
if(cnt>=a[i].w) continue;
for(int j=a[i].v;j>=a[i].u,cnt<a[i].w;j--){
if(!vis[j]) cnt++,vis[j]++,ans++;
}
}
cout<<ans;
}
【一本通提高篇贪心】 喷水装置
题目大意
有 $n$ 个浇灌喷头。每个喷头都装在草坪中心线上(离两边各$\frac{W}{2}$米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。
请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?
贪心思路
这题怎么这么计几啊?
如图,每个喷水装置覆盖的区域不是它的直径,我们需要用勾股定理算出那个圆和那个方块的交集的距离,即$\sqrt{r^2-(\frac{w}{2})^2}$。
算出这个距离后,就是一道裸的区间覆盖问题了。
所以我们的贪心思路就是,先处理处每一个区间的左右端点(即$x-\sqrt{r^2-(\frac{w}{2})^2}$和$x+\sqrt{r^2-(\frac{w}{2})^2}$),然后按左端点排序,依次处理即可,细节部分看代码。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=15010;
int T,n,m;
double l,w;
struct node{
double l,r;
}a[N];
bool cmp(node a,node b){
return a.l<b.l;
}
void work(){
m=0;
cin>>n>>l>>w;
for(int i=1;i<=n;i++){
double id,r;
cin>>id>>r;
if(r<=w/2) continue;
double d=sqrt(r*r-w*w/4.0);
a[++m]={id-d,id+d};
}
sort(a+1,a+1+m,cmp);
double now=0;
int cnt=0,i=1;
while(now<l){
cnt++;
double tmp=now;
while(a[i].l<=tmp&&i<=m) now=max(now,a[i].r),i++;
if(tmp==now&&tmp<l){
cout<<-1<<endl;
return;
}
}
cout<<cnt<<endl;
}
int main(){
cin>>T;
while(T--) work();
return 0;
}
【一本通提高篇贪心】 加工生产调度
题目大意
有$n$个物品需要加工,每个物品先在$A$车间加工再到$B$加工,问最短加工时间。
贪心策略
按每个物品在$A$和$B$车间的加工时间的最小值排序,然后模拟即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
struct node{
int a,b,id;
}a[N];
int w[N];
bool cmp2(node a,node b){
return min(a.a,b.b)<min(a.b,b.a);
}
bool cmp1(node a,node b){
return min(a.a,a.b)<min(b.a,b.b);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].a,a[i].id=i;
for(int i=1;i<=n;i++) cin>>a[i].b;
sort(a+1,a+1+n,cmp1);
for(int i=1,l=0,r=n+1;i<=n;i++){
if(a[i].a<a[i].b) w[++l]=a[i].id;
else w[--r]=a[i].id;
}
int s1=0,s2=0;
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++){
s1+=a[i].a;
s2=max(s1,s2);
s2+=a[i].b;
}
cout<<s2<<endl;
for(int i=1;i<=n;i++) cout<<w[i]<<" ";
}
【一本通提高篇贪心】 智力大冲浪
题目大意
有一些任务,每个任务都有完成期限,完不成一个任务就要扣一些钱,问最多能得到多少钱。
贪心策略
直觉上,如果要扣钱最少,肯定得让扣钱多的排到前面去,然后按照时间依次完成任务。
但是这样做是错误的(通过样例就能得出结论),所以我们需要优化一下这个思路。
我们可以用最优贪心,每个任务都在完成期限的最后一秒完成,用一个数组记录下每个时间点有没有被一个任务占用,然后向前找到最后一个能用的时间即可。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=510;
struct node{
int t,x;
}a[N];
bool cmp(node a,node b){
return a.x>b.x;
}
int n,m,tim[N];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>a[i].t;
for(int i=1;i<=n;i++) cin>>a[i].x;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=a[i].t;j;j--){
if(!tim[j]){
tim[j]=1,a[i].x=0;
break;
}
}
}
for(int i=1;i<=n;i++) m-=a[i].x;
cout<<m;
}
【一本通提高篇贪心】 数列极差
题目大意
有$n$个正整数,每次删去两个数$a,b$,放入一个数$a\times b+1$,问最后得到的一个数的最大值和最小值。
贪心策略
我们会发现这题很像之前的例题果子合并,所以我们可以考虑用堆维护。
而我们要同时维护最大值和最小值,可以用一个大根堆和一个小根堆。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=20;
priority_queue<int,vector<int>,greater<int>>a;//大根堆
priority_queue<int,vector<int>,less<int>>b;//小根堆
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int t;
cin>>t;
a.push(t),b.push(t);//分别加入两个中
}
//分别进行两个堆的维护过程,具体过程很像果子合并
while(a.size()>1){
int tmp=a.top();
a.pop();
tmp*=a.top();
a.pop();
a.push(tmp+1);
}
while(b.size()>1){
int tmp=b.top();
b.pop();
tmp*=b.top();
b.pop();
b.push(tmp+1);
}
cout<<a.top()-b.top();//输出题目要求维护的极差
}
【一本通提高篇贪心】 数列分段
题目大意
给定的一个正整数数列 ,现要将其分成连续的若干段,并且每段和不超过$m$,问最少分成几段。
贪心策略
这题就是最简单的贪心了,枚举的过程中累加和,如果超过$m$就情况,然后段数$+1$,没有什么思维含量。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,m,s=0,cnt=0;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t;
if(s+t>m) s=0,cnt++;
s+=t;
}
cout<<cnt+1;
}
【一本通提高篇贪心】 线段
题目大意
在一个数轴上有$n$条线段,现要选取其中$k$条线段使得这$k$条线段两两没有重合部分,问最大的$k$为多少?
贪心策略
即不相交区间问题,和习题第一道几乎一模一样,这里直接上代码。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int l,r;
}a[N];
bool cmp(node a,node b){
return a.r<b.r;
}
int n,k=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
sort(a+1,a+1+n,cmp);
int t=0;
for(int i=1;i<=n;i++){
if(a[i].l>=t) t=a[i].r,k++;
}
cout<<k;
}
【一本通提高篇贪心】 家庭作业
题目大意
有一些作业,每个作业有完成期限,每个作业完成会得到一定的学分,问最多能得到多少学分。
贪心策略
我们会发现这道题和智力大冲浪那题很像,但是那题做法的时间复杂度是$O(n^2)$,但这题的数据范围是$10^6$,所以需要优化。
一种优化方式是用并查集优化,并查集数组记录下最远能够追溯到的放置时间,如果用路径压缩优化的话,时间复杂度可以达到$O(\alpha n)$,其中$\alpha \le5$
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int t,x;
}a[N];
bool cmp(node a,node b){
return a.x>b.x;
}
int n,m,tim[N],fa[N],ans=0;
int find(int x){
//并查集查询
if(x==fa[x]) return x;//路径压缩
return fa[x]=find(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].x;
m=max(m,a[i].t);
}
for(int i=0;i<=m;i++) fa[i]=i;//初始化并查集
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
int d=find(a[i].t);
if(d) fa[d]=d-1,ans+=a[i].x;
}
cout<<ans;
}
【一本通提高篇贪心】 糖果传递
题目大意
有$n$个小朋友坐成一圈,每人有$a_i$个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为$1$。求使所有人获得均等糖果的最小代价。
贪心策略
本题需要一定的数学推导,比较繁琐,这里暂时略过,读者可以去找网上的题解。
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N],s[N],sum=0;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
for(int i=2;i<=n;i++){
s[i]=s[i-1]+a[i]-sum/n;
}
sort(s+1,s+1+n);
int mid=s[n/2+1],ans=0;
for(int i=1;i<=n;i++) ans+=abs(s[i]-mid);
cout<<ans;
}
ORZ
Orz
大家可以看他的博客:
luhaoren.xyz
几何画板好评