贪心知识点及例题选讲

定义

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

局限性

我们就以数字三角形为例。

       5
     3   7
   17  19  22
1000  15  21  33

贪心做法：每一步都走最大的，路线：$5-7-22-33$，和为$67$

动态规划做法：路线：$5-3-17-1000$，和为$1025$

所以，对于每一道贪心的题，我们都要尽可能证明其正确性，有的显然，但有的就不是，需要严谨的数学推理。

例题选讲

例$1.$游戏通关

传送门

提示：先做出$O(nT)$的算法，再考虑优化至$O(nlogn)$

例$2.$扑克牌

传送门

提示：可以先从没有特殊牌的情况考虑，再慢慢扩展。

例$3.$堆蛋糕

传送门

提示：先分类讨论，读入是本题的时间瓶颈

例$4.$楼间跳跃

传送门

提示：试着将每栋楼抽象成一个特殊的图

例$5.$皇后游戏

传送门

提示：这道题与流水作业调度问题是否有相似之处呢？

Solution

例1

贪心策略：

$1.$优先做利益大的任务。

$2.$对于一个任务的时间$[1,t_i]$，那么我们将这个任务尽量往靠近$t_i$的时间放。

证明：对于$1$，由于每个任务的时间都是$1$，所以各任务间互不影响，能够影响我们最终利益的只有该任务所能产生的利益，对于一个时间点$t_i$，假设同时有多个任务都可以在这个时间点完成，其利益分别为$w_1,w_2,...,w_n$，那么我们放大的肯定比放小的对全局做的贡献优。

对于$2$，因为所有任务的开始时间均为$1$，也就意味着所有任务时间的交集都集中在前面部分，那么我们如果要做一个任务，只有将其尽量往后放，以不占用尽量多任务的时间。

代码也很简单，先sort一遍，再对于每个任务的时间段$[1,t_i]$，我们从$t_i$开始枚举到$1$，有空位就放，加入最终答案，如果无空位就证明该任务无法完成。

#include<cstdio>
#include<algorithm>
using namespace std;
struct ben{
    int t,val;
}a[505];
int vis[505];
int cmp(const ben &a,const ben &b){
    return a.val>b.val;
}
int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].t);
    } 
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].val);
    } 
    sort(a+1,a+n+1,cmp);
    int ans=0,t=0;
    for(int i=1;i<=n;i++){
        for(int j=a[i].t;j;j--){
            if(vis[j]==0){
                vis[j]=1;
                ans+=a[i].val;
                break;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

时间复杂度$O(nT)$

考虑优化上述程序，我们发现大部分时间全部花费在了对$t_i$前的空位的寻找，所以我们可以用一个$last$数组来记录每个数前面最靠近它的空位，查询时直接调用，修改时直接找离填的那个空位的前一个数最近的空位，时间复杂度变为$O(1)$。

由于有$sort$，故时间复杂度为$O(nlogn)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],lst[200005],ans=0;
struct node{
	int a,b;
}f[200005];
bool cmp(node x,node y){
	return x.b>y.b;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&f[i].a,&f[i].b);
	}
	sort(f+1,f+n+1,cmp);
	for(int i=1;i<=200000;i++){
		lst[i]=i;
	}
	for(int i=1;i<=n;i++){
		if(lst[f[i].a]){
			ans+=f[i].b;
			lst[f[i].a]=lst[lst[f[i].a]-1];
		}
	}
	cout<<ans<<endl;
}

例2

先考虑不取特殊牌的情况，那么我们最多可以凑$min(a_1,a_2,...a_n)$副牌。

取完后，牌组里还剩$a_1^{\prime },a_2^{\prime },...,a_n^{\prime }$张牌。

贪心策略：选取$min(剩余特殊牌张数,未放特殊牌的牌堆数)$张特殊牌来替代未放特殊牌的牌堆里的一张普通牌。每次替代时选取$a_1^{\prime },a_2^{\prime },...,a_n^{\prime }$中最小的数，用一张特殊牌来替代。

证明：由于特殊牌在这里的作用是代替一张普通牌，由于最多每堆牌拿出一张，所以特殊牌最多拿出当前未放特殊牌的牌堆数目这么多张。为了凑出尽量多堆牌，如果我们将特殊牌给到张数不是最小的一种牌身上，那么答案一定不会更优，因为我们可以凑出的牌的张数是由张数最少的那一堆牌决定的。故将特殊牌放在最少的一种牌里可以使答案更优。

代码实现时我们使用一个小根堆，每次取出队首更新，并且记录两个全局变量表示现在没有放特殊牌的堆数与已经凑出的堆数，稍加处理即可。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
int Read(){
	int x;
	scanf("%d",&x);
	return x;
}
priority_queue<int,vector<int>,greater<int> > q;
int main(){
	n=Read(),m=Read();
	for(int i=1;i<=n;i++){
		a[i]=Read();
		q.push(a[i]);
	}
	int ans,rs;
	ans=rs=q.top();
	while(1){
		int tmp;
		for(int i=1;i<=rs;i++){
			if(!m)  break;
			tmp=q.top(),q.pop();
			q.push(tmp+1);
			m--;
		}
		tmp=q.top();
		if(tmp-ans==0)  break;
		rs=tmp-ans;				//未放特殊牌的堆数
		ans=tmp;				//已经凑出的堆数
		if(!m)  break;
	}
	cout<<ans<<endl;
}

例3

由于蛋糕是$3$层的，我们可以想到对蛋糕的个数相当于$n/3$的大小来进行分类讨论。

我们记$cn{t}_i$为半径为$i$的蛋糕个数，$cn{t}_i$的最大值为$maxn$，记该半径的蛋糕的半径为$x_1$，次大值为$y$，记该半径的蛋糕半径为$x_2$

我们分$3$种情况讨论：（下面的除法均为整除）

• $maxn>n/3,y\le n/3$

我们令$t=(n-maxn)/2$，先不考虑半径为$x$的蛋糕

当$y\le t$时：我们一定可以找到一种方案，使排名为$1-t$的蛋糕在上层，排名为$t+1-2t$的蛋糕在下层，因为次大值出现的次数小于$t/2$，那么不可能出现一个两层的蛋糕的上下两层均为同一尺寸的蛋糕。然后我们在半径为$x_1$的蛋糕里选$t$个放到最下层，容易证明这是一种最优的构造方式，此时答案为$t$。

当$y>t$时，我们放弃一些半径为$x_2$的蛋糕，使$y=t$，设我们去掉$q$个蛋糕，那么我们有：

$$(n-q-maxn)/2=y-q,解得q=maxn-n+2y$$

答案便为$y-q=y-maxn+n-2y=n-maxn-y$

• $maxn>n/3,y>n/3$

如果我们按照上文所述的分法，那么必定会出现有一组蛋糕上下大小相同，那么我们将另外的$n-maxn-y$个蛋糕分到不同的组内，再将半径为$x_1,x_2$的蛋糕每种$n-maxn-y$个与其他蛋糕配对，答案为$n-maxn-y$

• $maxn<n/3,y<n/3$

这时我们将排名为$1-n/3$的蛋糕放上层，$n/3+1-2n/3$的蛋糕放中层，$2n/3+1-3n$的蛋糕放上层，一定可以满足条件，此时答案为$n/3$。

由于$n$较大，注意使用快速的读入方式。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
inline int Read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))  ch=getchar();
	while(isdigit(ch))  x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
int n,cnt[3000005];
int main(){
	n=Read();
	int x,j=0,k=n/3,y=0,ans;
	for(register int i=1;i<=n;++i){
		x=Read();
		cnt[x]++;
	}
	for(register int i=1;i<=n;++i){
		if(cnt[i]>j){
			y=j;
			j=cnt[i];
		}
		else if(cnt[i]>y)  y=cnt[i];
	}
	if(j>k&&y<=k){
		if(y<=(n-j)/2)  ans=(n-j)/2;
		else  ans=n-j-y;
 	}
	else if(j>k&&y>k)  ans=n-j-y;
	else  ans=k;
	printf("%d\n",ans);
}

例4

考虑把每栋楼看做一个环，易得如果从环$i$跳到环$i+1$，那么再跳回来一定不是最优解。

所以我们的问题变为：现在有$n$个环，你有$m$的时间，对于每一个环可以花费$k$单位时间来获得$k\ast v_i$的价值，或跳到另一个环，获得$v_{i+1}$的价值。

枚举每一个环作为终点，那么我们有$j-1$的时间在环间跳，有$m-j+1$的时间在环上。

考虑贪心，我们使用一个堆，堆首为$v$最小的元素，使得环的高度小于等于或者刚好大于$m$，那么我们记录当前堆里元素的价值和，计算时只需要减去堆顶超出的部分即可。

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define pii pair<int,int>
using namespace std;
inline int Read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')  f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m,h[1000005],v[1000005],ans=0,maxn=0,sz=0,res=0;
priority_queue<pii,vector<pii >,greater<pii > > q;
inline int my_min(int x,int y){
	return (x>y)?y:x;
}
signed main(){
	n=Read(),m=Read();
	m++;
	for(int i=1;i<=n;i++){
		h[i]=Read();
		v[i]=Read();
	}
	for(int i=1;i<=n;i++){
		m--;
		res+=v[i];
		if(!m)  break;
		if(h[i]==1)  continue;
		q.push(make_pair(v[i],h[i]-1));
		sz+=h[i]-1;
		ans+=v[i]*(h[i]-1);
		while(!q.empty()&&sz-q.top().second>=m){
			sz-=q.top().second;
			ans-=q.top().first*q.top().second;
			q.pop();
		}
		int tmp=res+ans;
		if(sz>=m){
			tmp-=q.top().first*q.top().second;
			tmp+=(m-sz+q.top().second)*q.top().first;
		}
		maxn=max(maxn,tmp);
	}
	cout<<maxn<<endl;
}

例5

题解链接