算法模板：经典贪心问题
什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
这便是 “贪” 字的由来，考虑局部最优解便是贪心思想的精髓。
其实 此次有一点 标题 党的嫌疑了，因为贪心问题并没有一个通用的模板。
大多数的贪心思想 其实很容易想出来，但难的是证明这样做法的正确性，所以建议读者做贪心问题时，不要从大量时间 来推理解法的正确性，可以换种思路，尝试举出 与解法相悖的反例，如果列举不出反例，则解法应该是没问题的。
区间问题
1.按左端点或右端点排序
2.寻找性质
区间选点
给定 N 个闭区间 [a i,b i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。位于区间端点上的点也算作区间内。
输入格式
第一行包含整数 N，表示区间数。接下来 N
行，每行包含两个整数 a i,b i，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤105
−109≤a i≤b i≤109
输入样例：
3 -1 1 2 4 3 5
输出样例：
2
题解部分：
贪心思路
1.先将每个区间按右端点从小到大排序
2.然后每次枚举每个区间，当某个区间内已经取了点时，直接跳过即可，否则取每个区间最右端的端点。
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; struct PII{ int l,r; }s[N]; bool cmp(PII a,PII b) { return a.r<b.r; } int main() { int n; cin>>n; for(int i = 0 ; i < n ; i ++) cin>>s[i].l>>s[i].r; sort(s,s+n,cmp); int ans = 0, ed= -2e9+10; for(int i = 0 ; i < n ; i ++) if(ed<s[i].l) { ed=s[i].r; ans++; } cout<<ans; return 0; }
区间数量
给定 N 个闭区间 [a i,b i]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤105,
−109≤a i≤b i≤109
输入样例：
3 -1 1 2 4 3 5
输出样例：
2
题解部分：
和上一题 可以说是完全一样了
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; struct PII{ int l,r; }s[N]; bool cmp(PII a,PII b) { return a.r<b.r; } int main() { int n; cin>>n; for(int i = 0 ; i < n ; i ++) cin>>s[i].l>>s[i].r; sort(s,s+n,cmp); int ans = 0, ed= -2e9+10; for(int i = 0 ; i < n ; i ++) if(ed<s[i].l) { ed=s[i].r; ans++; } cout<<ans; return 0; }
排队接水
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小 ？
输入样例：
7 3 6 1 4 2 5 7
输出样例：
56
数据范围
1≤n≤10 ^5
1≤t i≤10^4
题解部分：
坑点1 ：此题让求解的是等待时间，不算自己接水的时间
坑点2：所有人的等待时间之和，所以需要求解每一个人的等待时间后再累加一遍
坑点3：虽然题目范围 是 10^4 但经过10^5的累加 必然 会爆int 所以需要用 long long
贪心思想：
按等待时间 从小到大排序，用时少的先接水
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; long long s[N],sum,ans; int main() { int n,m; cin>>n; for(int i = 0 ;i < n ; i ++) cin>>s[i]; sort(s,s+n); for(int i = 0 ;i < n - 1; i ++) { sum+=s[i]; ans+=sum; } cout<<ans; return 0; }
耍杂技的牛
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 W i 以及自己的强壮程度 S i。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，
现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数 N，表示奶牛数量。接下来 N行，
每行输入两个整数，表示牛的重量和强壮程度，
第 i 行表示第 i 头牛的重量 W i 以及它的强壮程度 S i。
输出格式
输出一个整数，表示最大风险值的最小可能值。
数据范围
1≤N≤50000
1≤W i≤10,000,
1≤S i≤1,000,000,000
输入样例：
3 10 3 2 5 3 3
输出样例：
2
题解部分：
贪心思路：
我们先分析每头牛的危险值 = 他前面牛的w(重量值)和 - 自身的s(强壮值)，
要使每头牛的危险值最小，这显然是与w 和 s同时相关，
所以猜测出一种做法按 每头牛的w + s进行升序排序
然后依次从小到达 按层数由高到低的顺序来计算每头牛的危险值
#include <algorithm> #include <iostream> #define x first #define y second using namespace std; typedef pair<int, int> pii; const int N = 5e4 + 10; int n; pii a[N]; int main() { cin >> n; for (int i = 0; i < n; i++) { int w, s; cin >> w >> s; a[i] = {w + s, w}; } sort(a, a + n); int res = -1e9; for (int i = 0, sum = 0; i < n; i++) { int w = a[i].y, s = a[i].x - w; res = max(res, sum - s); sum += w; } cout << res << endl; return 0; }
完结散花
ok以上就是对 经典贪心问题 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
