贪心算法课堂笔记

一、今天学习了什么

今天的题目主要使用了“排序+贪心”。

贪心的做法是：

每一步都选择当前最合适的方案。

今天练习的主要题型：

1. 用最少的人或物品达到目标；
2. 在容量内尽量多拿物品；
3. 每组最多放两个物品；
4. 两组数据进行最优匹配；
5. 数字和字符串的贪心排列；
6. 删除数字后得到最大数或最小数；
7. 按单价排序后购买物品。

---

二、先判断排序方向

贪心题经常要先排序。最重要的是判断应该升序还是降序。

题目目标	常用排序方向
用最少数量达到目标	从大到小
容量一定，尽量多拿物品	从小到大
花钱尽量少	单价从小到大
每组最多两个，组数最少	从小到大，再用双指针
两组数据差值尽量小	两组都从小到大
拼接得到最大数	使用专门的字符串比较函数

升序：

sort(a,a+n);

降序：

sort(a,a+n,greater<int>());

做题前先问自己：

我应该优先选择大的，还是优先选择小的？

---

三、模型1：用最少数量达到目标

思考方法

希望选择的数量最少，就应该优先选择贡献最大的元素。

做法：

1. 从大到小排序；
2. 从前往后累加；
3. 第一次达到目标时停止。

通用模板

sort(a,a+n,greater<int>());
int sum=0,ans=0;
for(int i=0;i<n;i++){
	sum+=a[i];
	ans++;
	if(sum>=m) break;
}

对应题目

• 6377 赶工的Aki：选择最少的师傅完成零件；
• 4794 当总统：选择最少的州，并取得每个州刚好过半的选票。

赶工的Aki易错点

输入顺序是：

需要加工的零件数m
师傅人数n

如果所有师傅的加工量之和仍然不够，要输出：

NO

不能输出 -1。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int m,n,a[N];
int main(){
	cin>>m>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n,greater<int>());
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=a[i];
		if(sum>=m){
			cout<<i+1;
			return 0;
		}
	}
	cout<<"NO";
	return 0;
}

---

四、模型2：容量有限，尽量多拿

思考方法

每个物品都只计算“一个”，想让数量最多，就应该先拿最轻的。

做法：

1. 从小到大排序；
2. 依次尝试放入；
3. 放不下时停止。

sort(a,a+n);
int sum=0,cnt=0;
for(int i=0;i<n;i++){
	if(sum+a[i]<=x){
		sum+=a[i];
		cnt++;
	}else break;
}

对应题目：1932 淘淘捡西瓜。

对比记忆：

数量最少达到目标：先选大的。
容量有限数量最多：先选小的。

---

五、模型3：最轻和最重配对

独木舟问题

每条独木舟最多坐两个人，总重量不能超过 w，求最少独木舟数量。

先排序，再使用两个指针：

int l=0,r=n-1;

• l 指向最轻的人；
• r 指向最重的人。

每次先安排最重的人：

• 如果最轻的人能和他同坐，就让两人一起坐；
• 如果最轻的人都不能和他同坐，最重的人只能单独坐。

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int w,n,a[N];
int main(){
	cin>>w>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int l=0,r=n-1,ans=0;
	while(l<=r){
		if(l<r&&a[l]+a[r]<=w) l++;
		r--;//最重的人已经被安排
		ans++;
	}
	cout<<ans;
	return 0;
}

易错点

这道题不是“两数之和”。

题目没有要求找到两个人的体重和恰好等于 w，而是要求：

每条船不超重，并且船的数量最少。

所以判断条件是：

a[l]+a[r]<=w

不是：

a[l]+a[r]==w

---

六、模型4：刚好能赢的匹配

田忌赛马

把双方的马都从小到大排序。

sort(a,a+n);
sort(b,b+n);

用自己当前最慢的马 a[l]，尝试战胜对方当前最慢的马 b[r]：

• 如果 a[l]>b[r]，完成一次获胜匹配；
• 如果 a[l]<b[r]，自己的这匹马连对方最慢的马都赢不了，只能放弃。

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n,a[N],b[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	sort(a,a+n);
	sort(b,b+n);
	int l=0,r=0,ans=0;
	while(l<n&&r<n){
		if(a[l]>b[r]){
			ans++;
			l++,r++;
		}else l++;
	}
	cout<<ans;
	return 0;
}

输入易错点

这道题只有一个人数 n，双方都是 n 匹马。

不能写成：

cin>>n>>m;

正确写法：

cin>>n;

两组排序后一一匹配

如果要让两组数据的差值总和最小，就把两组都从小到大排序，再让相同位置配对。

sort(a,a+n);
sort(b,b+n);
for(int i=0;i<n;i++){
	ans+=abs(a[i]-b[i]);
}

对应题目：2058 滑翔翼。

---

七、模型5：分组贪心

1. 书架

每层最多放 m 本书，每层高度由最高的书决定。

把书从高到低排序，每 m 本放一层。每组第一本书最高，需要计入总高度。

sort(a,a+n,greater<int>());
int sum=0;
for(int i=0;i<n;i+=m){
	sum+=a[i];
}

对应题目：4797 书架。

2. 购书

每3本书中最便宜的一本免费。

为了让免费金额尽量大，应把价格从高到低排序，每连续3本分成一组。

sort(a,a+n,greater<int>());
long long ans=0;
for(int i=0;i<n;i++){
	if(i%3!=2) ans+=a[i];//每组第3本免费
}

这种写法不会访问数组范围外的位置，比依赖全局数组中的 0 更清楚、更安全。

对应题目：4799 购书。

3. 当总统

要赢得超过一半的州，先选择“拿下所需选票最少”的州。

一个州有 a[i] 名选民，拿下该州至少需要：

a[i]/2+1

先把州人数从小到大排序，再选择前：

m/2+1

个州。

---

八、模型6：按价格从低到高购买

1. 买饮料最省钱

每家店有单价和库存。要买恰好 m 瓶并使花费最少，就先去单价最低的店。

结构体：

struct fd{
	long long a,b;//a是单价，b是库存
};

比较函数：

bool f(fd s1,fd s2){
	return s1.a<s2.a;
}

每家店购买：

long long x=min(s[i].b,m);
ans+=x*s[i].a;
m-=x;

完整模板：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct fd{
	long long a,b;
};
fd s[N];
int n;
long long m,ans;
bool f(fd s1,fd s2){
	return s1.a<s2.a;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i].a>>s[i].b;
	sort(s,s+n,f);
	for(int i=0;i<n&&m>0;i++){
		long long x=min(s[i].b,m);
		ans+=x*s[i].a;
		m-=x;
	}
	cout<<ans;
	return 0;
}

2. 圣诞礼物

预算一定，希望买到的礼物数量最多，也应该先买单价低的礼物。

区别是：

饮料题：数量固定，求最少花费。
礼物题：预算固定，求最多数量。

两题都要按单价升序排序。

---

九、数字和字符串排序

1. 数字变位

组成最大数：数字从大到小排序。

组成最小数：数字从小到大排序，但最高位不能是 0。

sort(s.begin(),s.end());
for(int i=0;i<s.size();i++){
	if(s[i]!='0'){
		swap(s[0],s[i]);
		break;
	}
}

对应题目：1102 数字变位。

2. 拼接最大数

不能直接比较 a>b，因为需要判断谁放在前面能让拼接结果更大。

bool f(string a,string b){
	return a+b>b+a;
}

例如：

a="12"，b="121"
a+b="12121"
b+a="12112"

所以 12 应该放在 121 前面。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
string s[N];
int n;
bool f(string a,string b){
	return a+b>b+a;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>s[i];
	sort(s,s+n,f);
	if(s[0]=="0"){
		cout<<0;
		return 0;
	}
	for(int i=0;i<n;i++) cout<<s[i];
	return 0;
}

如果排序后第一项是 "0"，说明所有数字都是 0，直接输出一个 0。

---

十、删数字贪心

删数字时，剩余数字的相对顺序不能改变。

1. 删除后得到最大数

从左向右找到第一处：

s[i]<s[i+1]

删除较小的 s[i]，可以让更大的数字提前。

69134
6<9，先删除6

如果整个字符串从大到小排列，就删除最后一位。

对应题目：

• 4917 删除数字
• 6477 删除数字

2. 删除后得到最小数

从左向右找到第一处：

s[i]>s[i+1]

删除较大的 s[i]，可以让更小的数字提前。

如果整个字符串从小到大排列，就删除最后一位。

对应题目：1839 删数问题。

3. 两种方向不要混淆

求最大：前面小、后面大，删除前面的小。
求最小：前面大、后面小，删除前面的大。

4. 循环边界

程序会访问 s[i+1]，所以循环必须写：

for(int i=0;i<s.size()-1;i++)

不能写：

for(int i=0;i<s.size();i++)

否则最后一次会访问字符串外面。

5. 删除最小数的完整模板

#include<bits/stdc++.h>
using namespace std;
string s;
int k;
int main(){
	cin>>s>>k;
	while(k--){
		bool ok=0;
		for(int i=0;i<s.size()-1;i++){
			if(s[i]>s[i+1]){
				s.erase(i,1);
				ok=1;
				break;
			}
		}
		if(!ok) s.erase(s.size()-1,1);
	}
	while(s.size()>1&&s[0]=='0') s.erase(0,1);
	cout<<s;
	return 0;
}

判断前导零时，要先判断 s.size()>1，再访问 s[0]。

---

十一、重点订正：1091 最小字典序

题目特点

必须交换一次两个位置，使新字符串字典序最小。

为了让字符串尽量小，先寻找最靠左的、能够被更小字符替换的位置。

对于这个位置：

1. 选择右边最小的字符；
2. 如果最小字符出现多次，选择最靠右的一个进行交换。

90分代码的两个问题

问题1：记录字符位置的数组没有初始化。

局部数组：

int a[26];

里面的初始值不确定，必须先设为 -1：

for(int i=0;i<26;i++) a[i]=-1;

问题2：如果无法让字符串变小，不能总是交换前两个字符。

• 如果有相同字符，交换两个相同字符，字符串不变，这是最小的；
• 如果所有字符都不同并且已经升序，交换最后两个字符影响最靠后，结果最小。

正确代码

#include<bits/stdc++.h>
using namespace std;
string s;
int last[26];
int main(){
	cin>>s;
	for(int i=0;i<26;i++) last[i]=-1;
	for(int i=0;i<s.size();i++){
		last[s[i]-'a']=i;//记录每个字符最后出现的位置
	}
	for(int i=0;i<s.size();i++){
		for(char c='a';c<s[i];c++){
			if(last[c-'a']>i){
				swap(s[i],s[last[c-'a']]);
				cout<<s;
				return 0;
			}
		}
	}
	//无法变小时，优先交换两个相同字符
	for(int i=1;i<s.size();i++){
		if(s[i]==s[i-1]){
			cout<<s;
			return 0;
		}
	}
	//字符严格递增，交换最后两个字符
	swap(s[s.size()-2],s[s.size()-1]);
	cout<<s;
	return 0;
}

---

十二、今日题目与模型对应

题号	题目	使用的模型
4339	田忌赛马	排序后双指针匹配
3848	独木舟	最轻和最重配对
4797	书架	降序分组
4799	购书	每3本一组
1102	数字变位	数字字符排序、处理前导零
6787	拼接最大数	字符串拼接比较
4917	删除数字	删除后求最大数
6477
1839	删数问题	删除后求最小数
6377	赶工的Aki	从大到小凑目标
1932	淘淘捡西瓜	从小到大尽量多拿
6298	买饮料最省钱	按单价升序购买
4610	圣诞礼物	预算内先买便宜的
2058	滑翔翼	两组排序后一一匹配
1091	最小字典序	一次交换、最后位置
4794	当总统	选择代价最小的州

---

十三、考前快速复习

1. 看到题目先问

要求数量最少，还是数量最多？
应该先选大的，还是先选小的？
是否需要排序？
是否可以使用左右指针？

2. 双指针检查

l和r分别表示什么？
每一轮至少有一个指针移动吗？
循环条件是l<r还是l<=r？

3. 字符串检查

求最大还是求最小？
访问s[i+1]时，i有没有小于s.size()-1？
删除后要不要清除前导零？

4. 结构体排序检查

比较的是单价、数量还是总价？
升序和降序有没有写反？
乘法和答案是否需要long long？

最重要的四句话：

用最少数量达到目标，通常先选大的。
容量有限想多拿，通常先选小的。
每组最多两个，通常考虑最轻和最重配对。
删数字求最大和求最小，比较符号正好相反。