hi，大家好，从今往后我将会新开一个专栏，专门讲解c++中（当然算法这种东西通用，不单单是c++）的一些常用算法，今天先讲解贪心。废话不多说，直接上干货！

---

贪心的定义

先上官方定义：

贪心策略（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（最有利）的局部选择，从而希望导致结果是全局最优解的算法策略。其核心思想是“局部最优即全局最优”。

是不是没看懂，不知道啥样的一种逻辑？还是让小汉堡说句人话，举几个例子

官方定义翻译——让你从“晕”中解救出来

贪心策略，为啥叫策略不叫算法？这就要谈一谈啥是算法，啥是策略了。

• 算法是一种有严格确定的步骤的序列
• 策略是一种想法，没有严格的步骤

而贪心只是一种想法，没有想二分、动态规划一样的步骤，所以贪心只是一个策略。

贪心，顾名思义，就是生活中的贪心，有点想生活中只顾眼前利益不为以后着想的人（但是我没有说贪心不好的意思），每一次都在用当前的最优解，最后就获得了整个大问题的最好的答案，但是贪心并不能解决所有问题，就像生活中只顾眼前利益不为以后着想的人一样不一定最后能赢。

我有点怀疑这个算法是贪心的懒货发明的 哈哈哈！！

用贪心的例子——这个“贪婪的策略”能解决问题吗？

贪心算法一些问题上能够得到最优解，比如：

过年了，你来到爷爷奶奶家拜年，爷爷奶奶要给你压岁钱，一共有7张人民币，分别是：$100,100,100,50,10,5,1$，你可以挑5张,请问你选那几张获得的压岁钱最多？
这个问题的答案是:选择$100,100,100,50,10$这五张获得的钱最多，为啥选择这几张呢？因为这几张金额最大，放在一起金额一定最大。在这种场合下，你肯定不会**“孔融让梨“**而是做一个“贪心鬼”。这就是一种贪心的思想，每一次选择最大的金额，最后就获得了最多的压岁钱。

---

贪心的实现

知道了贪心的思想，让我们了解一下贪心是如何用c++写出来的吧！
实现贪心问题分以下几步：

• 读读问题，根据题目上的测试样例按照贪心的思想在脑海中模拟一下，看看这个问题是否能用贪心解决（我们在这里默认可以）
• 将题目问的问题拆分成一个个小问题，因为贪心需要求局部最优，所以我们应该将大问题分成好几个小问题，每个小问题就是一个局部，找出每个小问题的最优解，我们也许就能获得大问题的最优解
• 每算一个小问题是，找出最好的解法

只需要按照这几步，题就有答案了。但是我无法列出超详细的步骤，因为贪心毕竟是策略不是算法，没有固定的做法，但是有例题你们就不怕不理解了。

但是来一句最好的理解——你做贪心时一定要记住，把自己变成一个目光短浅的人，不要想“这一个小问题我获得了最优解，下一个问题呢？整体的大问题呢？” 只要这道能用贪心做，你就只管眼前的这个小问题，不要想未来和过去，只顾眼前的利益，眼前最好的答案，写下来一定是对的

废话太多，你就把自己想成贪婪的人，想想如何才能最贪

---

例题

小汉堡自出题目——压岁钱

这道是我自己出的，没有题目链接和测试题库

题目

题目描述

过年了，你来到爷爷奶奶家拜年，爷爷奶奶要给你压岁钱，一共有$n$张人民币，你可以挑5张,请问你最多获得多少压岁钱？

输入格式

一共$2$行
第1行：一个正整数$n$，表示奶奶拿出的压岁钱张数
第二行：一共$n$个正整数，用空格隔开，存在$a$数组里，表示$n$张人民币每一张的面额，$a[i]$就是第$i$张人民币的面额

输出格式

一个正整数，表示你能获得的最多的压岁钱

输入样例

7
1 50 100 100 5 10 100

输出样例

360

数据大小

$n\le 100$
$a[i]\le 10^3$

---

题目理解和解题思路

读完题了吧？是不是很熟悉？当然熟悉，我刚刚定义贪心的时候举得例子就和这道题大致一样。
题相信你们已经读懂了，我们直接开始讲这道题的思想

按照我写的步骤，先判断这道题可以不可以用贪心的思想写出来，仔细一想，我选择最大面额的钱，最终一定获得了最多的压岁钱，所以，这道题可以用贪心写出来！（你：那不废话嘛，你用这个题举例子，这道题肯定是用贪心写的呀！我：额，有道理）

接着我们需要将这个问题分成几个小问题，我分成了这5个问题：拿第一张的时候应该拿哪一张，拿第二张的时候应该拿哪一张，拿第三张的时候应该拿哪一张，拿第四张的时候应该拿哪一张，拿第五张的时候应该拿哪一张。

最后解决每个小问题，我们以测试样例为例子，准备见证“贪心鬼”的作用吧！

---

详细解释——分析我们的思想是：
在分析之前你们回顾一个贪心的核心

你做贪心时一定要记住，把自己变成一个目光短浅的人，不要想“这一个小问题我获得了最优解，下一个问题呢？整体的大问题呢？” 只要这道能用贪心做，你就只管眼前的这个小问题，不要想未来和过去，只顾眼前的利益，眼前最好的答案，写下来一定是对的

刚开始奶奶手中还有$1,50,100,100,5,10,100$这几张钱

第一次拿钱，我们选择所有的钱中最大的一张，选一张最大的就能保证第一次拿钱得到了最优的解，就是$100$拿在手里，此时还剩$1,50,100,100,5,10$

第二次都拿钱，我们应当选择剩下的钱中，面额最大的，那就是$100$，现在手里有$100,100$两张钱，还剩$1,50,100,5,10$

第三次拿钱，不用我啰嗦了，肯定选剩下中最大的一张（记住要贪哦），选$100$，手中有$100,100,100$，奶奶手中还剩$1,50,5,10$

最后两次拿钱，我考考大家：
第四次拿钱，选________，手中有__________，奶奶手中还剩______________。

第五次拿钱，选________，手中有__________，奶奶手中还剩______________。

最后，一共得到了________压岁钱。

代码

#include<bits/stdc++.h>
using namespace std;
int a[101];

bool cmp(int a,int b){
    return a>b;
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for(int i=1;i<=5;i++){
        ans+=a[i];
    }
    cout<<ans;
    return 0;
}

代码解析

第10~13行：输入$n$和$a数组$，没啥讲的
第14和5~7行：对a数组进行从打到小的排序，为啥要排序？因为我们每次都选择剩下的钱币中最大的，所以来个排序，后面直接循环获得前五大的钱币，其实就是每次获得奶奶手中的最大的钱。
第16~18行：循环获得前五大的钱币，累加到$ans$。
最后输出

---

习题

第一题：排队接水

题目

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

如果两个人接水的时间相同，编号更小的人应当排在前面。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例 #1

输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

说明/提示

$1\le n\le 1000$，$1\le t_i\le 10^6$，不保证 $t_i$ 不重复.

---

思路解析

这道题让你输出最短平均接水等待时间和最短平均等待时间的方案（也就是大家排队的顺序），要想平均等待时间短，每个人的等待时间就要就要尽可能的短。如何做到每个人的等待时间短呢？这又用上了贪心策略：我们发现接水时间短的人拍在前面，而接水时间短的排在后面可以做到每个排队时间相对最短，但是为啥呢？

我们拿上图为例子，来分析一下为什么！
如过我们从大到小排序，顺序是：$5,4,2,1$，这样排序的总共等待时间（就是每个人的等待时间加载一起）是25

我们再来看从小到大排序：$1,2,4,5$.

从小到大比从大到小花的时间少，其实这有道理，比如：第一个人的接水时间，后面的每个人都会记为等待时间的一部分，所以他小一点，后面的等待时间就会少，第二个人，第三个……都是越小越好，而且靠前排队人的接水时间会被记很多次，而排在后面就不会记很多，所以如果接水时间长的人排在前面会记的次数多，而排在后面就会记的次数少，所以从大到小排序

代码

#include<bits/stdc++.h>
using namespace std;
double ans=0;

struct aa{
	int time;
	int id;
}a[100001];

bool cmp(aa a,aa b){
	if(a.time!=b.time)
		return a.time<b.time;
	else
		return a.id<b.id;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].time;
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		cout<<a[i].id<<" ";
	}
	double sum=0;
	for(int i=1;i<=n;i++){
		ans+=sum;
		sum+=a[i].time;
	}
	printf("\n%.2lf",(double)ans/n);
	return 0; 
}

因为我们在讲算法，代码就不逐句讲解了，但是好心提醒一下大家，代码容易超时，用29~33行那样巧妙的写法不会哦！

第二题：选择K个任务的最大总分

这是力扣的题目
想要获得更好的阅读体验，看我的这一篇博文

题目链接

点击蓝字查看题目

思路分析

前置分析

学过贪心的一读题就知道这是一道贪心算法的题目 其实可以查看题目的标签

我们知道：想要获得最大的总分，就要使每一次做任务时获得的分数最大（贪心的基本思想：局部最优造就全局最优 前面的c++算法——贪心策略幽默详细讲解 原来贪婪也有作用（习题持续更新）讲过）而想要每一次获得更大的分数

• 如果第 i 个任务使用技巧 1 完成，你将获得 technique1[i] 分。
• 如果使用技巧 2 完成，你将获得 technique2[i] 分。

根据题目的描述，想要获得最优的答案，我们要使用能获得最大分数的技巧来完成任务，简单的来说：每次完成任务，选择能获得最大分数的技巧

初步考虑

但是，你接着往下读

你 必须 使用技巧 1 完成 至少 k 个任务（不需要是前 k 个任务）

这时候你蒙了：如果每次择能获得最大分数的技巧，那么不一定能够使用够k次技巧$1$，而如果先选择够k次技巧$1$剩下的再按照前面的规则选择，你又不知道前面的k个技巧$1$​选择哪k个才能使最后获得最大的总分

浅表的想，你想到可以选择前k个最大的technique1中的元素，这样应该可以使这k个任务获得最大的分值
but(但是)，我告诉你：不对！万一有那么一组数据，前k个最大的technique1元素对应的 technique2 的元素比这k个还要大，而稍微小一点的k个technique1元素对应的 technique2 的元素比它要小（它指稍微小一点的一些technique1元素）这时候明显选的前k个元素不符合得到最优答案的条件，而又有一种选法(刚说的)既满足题目的要求有满足获得最优答案的要求，这说明这种选法不是最优的，这个策略行不通！

深入分析

我们继续换一种思路，在刚刚举反例的过程中，我们想到了只需要选择$技巧1-技巧2$的差最大的k个技巧$1$​即可，剩下的再按照基本原则进行选择

举个题目中的例子分析一下 ：

technique1 = [5,2,10], technique2 = [10,3,8], k = 2

先求出所有的technique1[i]-technique2[i]，为：[-5,-1,2]
再降序排列得到：[2,-1,-5]
然后选择前k个即可，就是：[2,-1] 他们两个对应的是 technique1中的：[10,2]
最后按照基本的原则选择剩下的，就是 technique1中的5和technique2中的10 这一对，显然选择10。
得到答案$10+2+10=22$ 答案正确

疑惑解释

但是，认真思考的你提出了问题：“如果technique1[i] - technique2[i] 三个都是 -3，而k=2，随便选了两个-3，结果这两个负三对应的technique1[i]很小， technique2[i]很大，完美避开了最优，最大的分数啊！”

你是一个认真思考的人，很棒！但是你的这个质疑不对因为你怀疑我的缜密思考了！，我在想这个思路时也想到了这个问题，但是仔细一想其实不存在。

举个例子：
technique1 = [1,2,3], technique2 = [4,5,6], k = 2
这个例子就是你的“反例”，我们来试一下
如果选任务1和2用技巧1，则任务3用技巧2，总分 = $1+2+6=9$
如果选任务1和3，总分 = $1+3+5=9$
如果选任务2和3，总分 = $2+3+4=9$
答案不管如何选前k个都相同。

为啥呢？我解释一下道理：因为他们的差都相同，所以
选technique1小一点的，最后的technique2会刚好补上，
选technique1大一点的，最后的technique2会刚好拉低。
最后的答案还是一样的

代码实现

但是，完全模拟这个思路不太好写，technique1和technique2进过排序之后很难一一对应，并排除使用已经干过的任务，于是我们把思路做简化

所以我们这样写：
先把所有的technique2加起来，存进$ans$，并统计所有的technique1[i]-technique2[i]，装进一个数组$diff$，这里的$diff[i]$如果非得解释出一个意思的话，就是：使用技巧1之后对最终答案的影响，是整数就是往好的影响，是负数就是往坏的影响（看到后面你就懂了）
对$diff$进行降序排序
这时候先让$ans$累加上正的$diff$（因为所有的technique2加起来不一定就是最优的答案（这你们看到这里也都知道）而正的$diff$就是那些选技巧1更优的任务比选技巧2多得的分值，加上它们也就是说把这些亏的分值补上（对最终的答案做好的影响），这些任务也就最优了，当然如果加的超过了k 也不用担心，毕竟是好的影响嘛，多出去更好）
如果现在累加上的$diff$还还不够$k$个的话，就继续累加到第$k$个$diff$元素（因为，为了满足题目中的要求，我们必须使用k次技巧1，而$diff[i]$代表的就是使用技巧1之后对最终答案的影响，也就是说，加到k就是把技巧1 使用到K次，把$diff$加到k就是把使用技巧1之后对最终答案的影响更新（不管是好的影响还是坏的影响），而对$diff$​进行降序排序就是为了让好的影响更多更大，尽量使用前k个的技巧1时不会出现坏的影响，即使出现也是更小的！只加到k个是因为，进到这种情况的，都是好的影响用完了，现在每多加一次都是对答案的进一步的坏影响，所以只加到k就好）
可能有点难懂，多读几遍，并结合下面的代码理解

根据这个简化的思路，实现一下代码：

class Solution {
private:
	static bool cmp(int x, int y) {
		return x > y;
	}
public:
	long long maxPoints(vector<int>& technique1, vector<int>& technique2, int k) {
		int n = technique1.size();
		vector<int> diff(n);
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			diff[i] = technique1[i] - technique2[i];
			ans += technique2[i];
		}
		sort(diff.begin(), diff.end(), cmp);
		int posCount = 0;
		for (int i = 0; i < n && diff[i] > 0; ++i) {
			ans += diff[i];
			++posCount;
		}
		if (posCount < k) {
			for (int i = posCount; i < k; ++i) {
				ans += diff[i];
			}
		}

		return ans;
	}
};

由于这个题主要讲解思路算法，而且代码中没有出现罕见语法和一些巧妙的写法，所以不对代码进行逐句解析

---

更新日志

• 2025年7月30日完成编写
• 2626年2月23日更新习题第二题

总结

今天我们学习了贪心策略，并且给大家讲解了一个例题，提供了一个习题，建议大家多找一些题练一练
我是小汉堡，希望你可以点赞加收藏哦！