一、考察频率以及难度
考察频率：⭐⭐⭐⭐
笔试题难度：⭐⭐⭐
算法难度：⭐
贪心算法是面试和笔试中非常常见的考察题型之一。它广泛应用于各种实际问题场景中，无论是在数组、字符串处理，还是在图论、区间调度等问题里都可能出现。
贪心算法本身的思想并不复杂，它的核心在于每一步都做出当前看起来最优的选择，期望通过局部最优来达到全局最优。不过，判断一个问题是否可以使用贪心算法求解，以及如何设计贪心策略是考察的重点和难点。
二、学习技巧
理解贪心本质：深入理解贪心算法的核心思想，即每一步都选择当前状态下的最优解。要明确贪心选择和最优子结构这两个关键要素，贪心选择是指问题的全局最优解可以通过一系列局部最优解得到，最优子结构是指问题的最优解包含其子问题的最优解。
分析问题特征：学会分析问题的特征，判断该问题是否适合使用贪心算法。一般来说，如果一个问题具有贪心选择性质和最优子结构性质，那么就可以尝试使用贪心算法求解。例如，在一些资源分配、区间调度等问题中，往往可以通过贪心策略得到最优解。
多做练习题：通过大量的练习题来熟悉不同类型的贪心问题，掌握常见的贪心策略和解题思路。在做题过程中，要注意总结归纳，分析每个问题的特点和贪心策略的选择依据。
学会猜结论：很多贪心的题目，策略可能不复杂，只是比较难证明正确性，因此在多做练习题的同时，一定要注意找到猜贪心结论的题干，拿到贪心题目时最好脑海中先能有几种候选的贪心策略，然后逐一验证。
验证贪心策略：在设计出贪心策略后，要通过严格的证明或者反例来验证该策略是否能得到全局最优解。有时候，局部最优选择并不一定能导致全局最优，所以需要谨慎验证。
三、应用场景
对于暴力的做法会超时、动态规划不好设计状态等问题时，不妨看下能否找到一种贪心策略来解决。
对于区间问题、资源分配问题、或是一些图论问题时，可以考虑贪心算法。
四、算法讲解
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。
算法步骤：
问题分析：明确问题的目标和约束条件，判断问题是否具有贪心选择性质和最优子结构性质。
设计贪心策略：根据问题的特点，设计一个贪心策略，即每一步如何做出最优选择。
执行贪心算法：按照贪心策略，逐步做出选择，直到得到问题的解。
验证解的最优性：通过证明或者反例来验证所得到的解是否是全局最优解。
例题：
在一个国家，流通着多种不同面值的货币。现有不同面值的硬币，其面值分别为 [1, 5, 10]（单位：元）。当顾客购物后，收银员需要找给顾客一定金额的零钱。请编写一个程序，计算出使用最少数量的硬币来凑出给定找零金额的方案，并输出所需硬币的最少数量。（硬币数量无限）
分析思路：
由于需要使用最少的数量凑出目标金额，因此不难想到贪心策略是优先找零的金额越大越好，因此只需要能用10就用10，对剩下的金额再能用5就用5，最后剩下的用1来找零。但是如何证明这样贪心的正确性呢？其实这题之所以可以用贪心，还有一个关键的特点：观察题目给的硬币金额，5可以只由1凑出，10可以只由5或只由1凑出，因此可以这样贪心。
试想，如果硬币面值有25元的，还可以这样做吗？（比如顾客购买31元的商品，最佳方案是什么？）
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
index = 0
while amount > 0:
if coins[index] <= amount:
num = amount // coins[index]
count += num
amount -= num * coins[index]
index += 1
return count
# 测试代码
coins = [10, 5, 1]
amount = 63
print(coin_change(coins, amount))另外补充一点，很多贪心的题目其实都有对应的动态规划做法，但是对于一些题目，贪心写起来会方便一些。对于明显可以贪心的题目，为了在笔试中节省宝贵的时间，最好直接选择贪心法。
五、例题解析
5.1 基础-坐船问题1
https://oj.niumacode.com/problem/P1394
有n个人和m条船，每条船最多只能做一个人，给定每个人的重量以及每条船的载重，问最少需要选择总载重为多少的船，可以把n个人运送过去？（n<=m<1e5）
如果运送不过去，请输出-1。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[100005], b[100005];
int main() {
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i];
// 对人的重量数组和船的载重数组进行排序
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int totalLoad = 0;
int boatIdx = 1;
int i = 1;
for(; i<=n; i++) {
while(boatIdx <= m && b[boatIdx] < a[i]) boatIdx++;
if(boatIdx > m) break;
totalLoad += b[boatIdx];
}
if(i <= n) cout << -1 << endl;
else cout << totalLoad << endl;
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
m = int(input())
b = [0] + list(map(int, input().split()))
# 对人的重量数组和船的载重数组进行排序
a.sort()
b.sort()
totalLoad = 0
boatIdx = 1
i = 1
while i <= n:
# 找到能承载当前人的最小载重的船
while boatIdx <= m and b[boatIdx] < a[i]:
boatIdx += 1
# 如果没有合适的船，退出循环
if boatIdx > m:
break
totalLoad += b[boatIdx]
i += 1
# 如果还有人没有船可坐，输出 -1
if i <= n:
print(-1)
else:
print(totalLoad)5.2 基础-坐船问题2
https://oj.niumacode.com/problem/P1395
小牛班级里有n位同学参加春游，给出每位同学的重量a[i]，现在进行划船比赛，每艘船两位同学，问如何分组，可以使得分组后最大载重的那艘船的载重最小？输出这个载重。(n<1e5,a[i]<=1e5)
输入
4
1 2 5 8
输出
9题解和代码
贪心思路：最大和最小的匹配，第二大和第二小的匹配，以此类推。
题目转化成：给定一个n个数的无序数组，每个值a[i]，最大和最小的匹配为一个小队，第二大和第二小的匹配为一个小队，以此类推，在计算的同时维护最大值即是答案。
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100005], b[100005];
int ans = 0;
int main()
{
cin>>n;
for(int i = 1; i<=n; i++) {
cin>>a[i];
}
sort(a+1, a+n+1);
for(int i = 1; i<=n; i++) {
int t = a[i]+a[n-i+1];
ans = max(ans, t);
}
cout << ans << endl;
return 0;
} n = int(input())
a = [0] + list(map(int, input().split()))
a[1:] = sorted(a[1:])
ans = 0
# 遍历元素，计算两两组合的和，并更新最大和
for i in range(1, n + 1):
t = a[i] + a[n - i + 1]
ans = max(ans, t)
# 输出最大和
print(ans)5.3 基础-坐船问题3
https://oj.niumacode.com/problem/P1396
小牛班级里有n位同学参加春游，给出每位同学的重量a[i]，现在进行划船比赛，每艘船最多两位同学，每艘船最多载重为x ，请输出想要承载所有人所需的最小船数。（n<1e5,a[i],x<=1e9）
输入
4 3
1 3 2 2
输出
3题解与代码
考虑贪心，由于每位同学都要上船，因此肯定一轻一重搭配最好，定义左右两个指针分别从两端向中间靠拢收敛。
对于当前左右指针，有两种情况：
如果无法同乘一艘船，则右指针（较重者）肯定无法与其他任意一个人同乘一艘船，因此他自己单独乘船，原问题答案为求解剩余 n-1 人所需最小船数加一。（左指针不动，右指针--）
若能与最重者同乘，为最优选择，去掉最轻和最重者，原问题答案为求解剩余 n-2 人所需最小船数加一。（左指针++，右指针--）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int limit, n;
cin >> n >> limit;
vector<int> people;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
people.push_back(num);
}
int ans = 0;
sort(people.begin(), people.end());
int light = 0, heavy = people.size() - 1;
while (light <= heavy) {
if (people[light] + people[heavy] > limit) {
--heavy;
} else {
++light;
--heavy;
}
++ans;
}
cout << ans << endl;
return 0;
}n, limit = map(int, input().split())
people = list(map(int, input().split()))
people.sort()
ans = 0
# 初始化轻量级和重量级人员的索引
light = 0
heavy = len(people) - 1
# 模拟将人员分配到船上的过程
while light <= heavy:
if people[light] + people[heavy] > limit:
# 如果最轻和最重的人不能一起上船，让最重的人单独上船
heavy -= 1
else:
# 如果最轻和最重的人能一起上船，他们一起上船
light += 1
heavy -= 1
# 每分配一次，所需船的数量加 1
ans += 1
# 输出所需船的总数
print(ans)5.4 基础-硬币向上
https://oj.niumacode.com/problem/P1400
有n枚硬币排成一排，用0表示反面，用1表示正面，每次操作需要翻转连续的三个硬币，问至少多少次操作可以使得所有硬币正面向上，如果无法做到请输出-1。(n<1e5)
输入
4
0 1 1 0
输出
2题解与代码
最左边一个如果是0的话，一定要翻转最左边3个（这一步是必须做的，因为只有这样才可以让最左边变成1），最左边如果是1的话，则一定不翻（这也是必须的）。此时问题就转化为n-1的相同子问题，以此类推求解。
#include <iostream>
#include <vector>
using namespace std;
int n;
int a[100005];
int main() {
cin >> n;
for(int i = 1; i<=n; i++) cin>>a[i];
int ans = 0;
for (int i = 1; i<=n; i++) {
if (a[i] == 0) {
if (i > n-2) {
cout << -1 << endl;
return 0;
}
for (int j = i; j < i + 3; j++) {
a[j] = 1 - a[j];
}
ans++;
}
}
cout << ans << endl;
return 0;
}n = int(input())
a = [0] + list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
# 如果当前元素为 0
if a[i] == 0:
# 如果当前位置往后不足 3 个元素，无法完成操作，输出 -1 并结束程序
if i > n - 2:
print(-1)
break
# 对当前位置及往后两个位置的元素进行取反操作
for j in range(i, i + 3):
a[j] = 1 - a[j]
# 操作次数加 1
ans = ans + 1
else:
# 如果没有执行 break 语句，说明可以完成操作，输出操作次数
print(ans)5.5 进阶-小牛选择最大卡牌
https://oj.niumacode.com/problem/P1397
小牛和小马在玩一种游戏，该游戏中双方各抽n张卡牌，每张卡牌都是一个小于1e5的正整数，谁的卡牌之和最大谁赢。小牛十分想赢，但是他想赢的漂亮，他希望自己选择的卡牌之和是3的倍数，宁可放弃一些卡牌。问在满足小牛的想法的前提下，他可以获得的最大卡牌之和是多少？
输入
5
1 3 3 3 6
输出
15题解与代码
本题思路很多，对于取模类题目，比较经典的是基于模数来维护信息，并使用动态规划来递推。当然，本题中也可以使用贪心的思想。
假设所有卡牌之和是3的倍数，那么不需要放弃卡牌；
假设所有卡牌之和%3=1，则要么丢弃一张%3=1的，要么丢弃两张%3=2的。
假设所有卡牌之和%3=2，则要么丢弃一张%3=2的，要么丢弃两张%3=1的。
因此，基于这个思路，我们只需要维护每个模数下的所有卡牌，从小到大排序贪心选择丢弃即可。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[100005];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin>>a[i];
}
vector<int> v[3];
long long tot = 0;
for (int i = 1; i <= n; i++) {
v[a[i] % 3].push_back(a[i]);
tot += a[i];
}
sort(v[1].begin(), v[1].end(), greater<int>());
sort(v[2].begin(), v[2].end(), greater<int>());
int remove = 1e9;
if (tot % 3 == 0) {
remove = 0;
}
else if (tot % 3 == 1) {
if (v[1].size() >= 1) {
remove = min(remove, v[1].back());
}
if (v[2].size() >= 2) {
remove = min(remove, v[2].back() + *(v[2].end() - 2));
}
}
else {
if (v[1].size() >= 2) {
remove = min(remove, v[1].back() + *(v[1].end() - 2));
}
if (v[2].size() >= 1) {
remove = min(remove, v[2].back());
}
}
cout << tot - remove << endl;
return 0;
}# 读取数组长度
n = int(input())
# 读取数组元素
a = [0] + list(map(int, input().split()))
# 初始化三个列表来存储余数为 0、1、2 的元素
v = [[] for _ in range(3)]
# 计算所有元素的总和
tot = 0
# 遍历数组，将元素按余数分类，并计算总和
for i in range(1, n + 1):
remainder = a[i] % 3
v[remainder].append(a[i])
tot += a[i]
# 对余数为 1 和 2 的列表进行降序排序
v[1].sort(reverse=True)
v[2].sort(reverse=True)
# 初始化要移除的元素总和为无穷大
remove = float('inf')
# 根据总和的余数情况计算要移除的元素总和
if tot % 3 == 0:
remove = 0
elif tot % 3 == 1:
if len(v[1]) >= 1:
remove = min(remove, v[1][-1])
if len(v[2]) >= 2:
remove = min(remove, v[2][-1] + v[2][-2])
else:
if len(v[1]) >= 2:
remove = min(remove, v[1][-1] + v[1][-2])
if len(v[2]) >= 1:
remove = min(remove, v[2][-1])
# 输出最终结果
print(tot - remove)5.6 进阶-最优任务分配（VIP）
https://oj.niumacode.com/problem/P1398
小牛是一个任务分配管理员，管理一个工厂，工厂里有若干个不同编号的任务，对应的任务量用数组a表示。
一开始，所有的工作岗位都处于未分配状态。小牛可以进行如下的任务分配操作任意次：
选择两个不同的且未分配的工作岗位编号 i 和 j，若满足 2 * a[i] <= a[j]，那么将这两个工作岗位标记为已分配。
可以执行上述操作任意次，计算出最多可以将多少个工作岗位标记为已分配状态。(n, a[i]<1e5)
输入
4
2 3 4 5
输出
2题解与代码
不难发现本题最多凑出n/2对(i,j)，因此把数组一分为二，其中i就从前一半中选，j从后一半中选，对于每一个i都保证找到一个最左的j与之匹配。因此用双指针向后遍历即可。其实这题也可以二分答案，感兴趣同学可以思考下看看
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
nums.push_back(num);
}
sort(nums.begin(), nums.end());
int m = nums.size() / 2;
int res = 0;
int i = 0, j = m;
while (i < m && j < nums.size()) {
while (j < nums.size() && 2 * nums[i] > nums[j]) {
j++;
}
if (j < nums.size()) {
res += 2;
j++;
}
i++;
}
cout << res << endl;
}n = int(input())
nums = list(map(int, input().split()))
nums.sort()
m = len(nums) // 2
res = 0
i = 0
j = m
# 开始循环，只要 i 小于 m 且 j 小于列表长度就继续
while i < m and j < len(nums):
# 当 j 小于列表长度且当前 i 位置元素的两倍大于 j 位置元素时，j 指针后移
while j < len(nums) and 2 * nums[i] > nums[j]:
j = j + 1
# 如果 j 仍在列表范围内，说明找到了符合条件的配对，结果加 2，同时 j 指针后移
if j < len(nums):
res = res + 2
j = j + 1
# i 指针后移
i = i + 1
# 输出最终结果
print(res)
5.7 进阶-小牛服务公司的最大利润（VIP）
https://oj.niumacode.com/problem/P1399
小牛有一家服务公司，公司里有 n 项服务项目和 m 个服务人员。每个项目都有对应的复杂程度a[i]以及对应的收益b[i]。每个服务人员都有自己的业务能力值c[i]，每个服务人员只能胜任复杂程度不超过其业务能力的服务项目。
一项服务可以被选择多次，每个人员最多选择一项服务，请问服务公司的最大收益是多大？（m<=n<=1e5,1<=a[i],b[i],c[i]<=1e5）
输入
4 3
1 2 3 4
20 10 30 40
1 2 3
输出
70题解与代码
把项目的复杂程度和收益打包后从小到大排序，然后维护前缀最大值，最后对服务人员排序后遍历，为他找一个复杂度不大于他的收益最高的项目（这一步可以双指针也可以二分），最后累加即可。
注意一些双指针顺序遍历的题目，其实都也可以用二分来考虑，只不过时间复杂度上会带一个log。
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int a[100005],b[100005],c[100005];
int n, m;
int main() {
cin >> n >> m;
for(int i = 1; i<=n; i++) cin>>a[i];
for(int i = 1; i<=n; i++) cin>>b[i];
for(int i = 1; i<=n; i++) cin>>c[i];
vector<pair<int, int>> jobs;
for(int i = 1; i<=n; i++) {
jobs.emplace_back(a[i], b[i]);
}
sort(jobs.begin(), jobs.end());
sort(c+1, c+m+1);
int j = 0, mx = 0;
long long ans = 0;
for (int i = 1; i<=m; i++) {
while (j < n && c[i] >= jobs[j].first) {
mx = max(mx, jobs[j].second);
j++;
}
ans += mx;
}
cout << ans << endl;
return 0;
}5.8 进阶-和为target的子数组数量（VIP）
给定一个长度为n的数组a，问最多可以选出多少互不重叠的子数组，使得这些子数组的和都为target。（n<1e5, 1e5<a[i],target<1e5）
输入
5 2
-1 1 1 1 1
输出
2思路与代码
贪心考虑对剩余子问题影响最小（副作用最小）的右端点，因此从左到右遍历，只要找到一段子区间为target则为候选答案。
证明可使用等价成立证明法：考虑如果有a[l,..,r1]和a[l,..,r2]都为target，如果a[l,..,r2]在最终答案中，则替换为子区间a[l,..,r1]，一定不会使得答案更差，也不影响后续其他选择，因此可以把a[l,..,r2]等价替换成a[l,..,r1]。
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
int n, target;
cin >> n >> target;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
int ret = 0;
int i = 0;
while (i < n) {
set<int> s = {0};
// 初始化当前前缀和
int total = 0;
while (i < n) {
// 累加当前元素到前缀和
total += nums[i];
// 检查是否存在满足条件的子数组
if (s.find(total - target) != s.end()) {
// 若存在，不重叠子数组数量加 1
++ret;
break;
} else {
// 若不存在，将当前前缀和加入集合
s.insert(total);
}
// 移动到下一个元素
++i;
}
// 无论是否找到满足条件的子数组，都移动到下一个位置开始新的查找
++i;
}
cout << ret << endl;
return 0;
}n, target = map(int, input().split())
nums = list(map(int, input().split()))
ret = 0
i = 0
while i < n:
s = {0}
total = 0
while i < n:
total += nums[i]
if total - target in s:
# 若存在，不重叠子数组数量加 1
ret += 1
break
else:
# 若不存在，将当前前缀和加入集合
s.add(total)
# 移动到下一个元素
i += 1
# 无论是否找到满足条件的子数组，都移动到下一个位置开始新的查找
i += 1
print(ret)