算法模板：

• 前言
• 什么是贪心
• • 区间问题
  • 区间选点
  • 区间数量
  • 排队接水
  • 耍杂技的牛
• 完结散花
• 参考文献

前言

⭐️感谢相遇，唤我沈七就好。
⭐️如果能和你一起进步那就太好啦。

什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

这便是 “贪” 字的由来，考虑局部最优解便是贪心思想的精髓。

其实 此次有一点 标题 党的嫌疑了，因为贪心问题并没有一个通用的模板。

大多数的贪心思想 其实很容易想出来，但难的是证明这样做法的正确性，
所以建议读者做贪心问题时，不要从大量时间 来推理解法的正确性，可以换种思路，尝试举出 与解法相悖的反例，如果列举不出反例，则解法应该是没问题的。

区间问题

1.按左端点或右端点排序

2.寻找性质

区间选点

给定 N 个闭区间 [a i,b i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 N，表示区间数。接下来 N

行，每行包含两个整数 a i,b i，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

1≤N≤105
−109≤a i≤b i≤109

输入样例：

3-1 12 43 5

输出样例：

2

题解部分：

贪心思路

1.先将每个区间按右端点从小到大排序

2.然后每次枚举每个区间，当某个区间内已经取了点时，直接跳过即可，否则取每个区间最右端的端点。

#includeusing 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 12 43 5

输出样例：

2

题解部分：

和上一题 可以说是完全一样了

#includeusing 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 个人装满水桶所需的时间是 t i，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小 ？

输入样例：

73 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

贪心思想：

按等待时间 从小到大排序，用时少的先接水

#includeusing 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

输入样例：

310 32 53 3

输出样例：

2

题解部分：

贪心思路：

我们先分析每头牛的危险值 = 他前面牛的w(重量值)和 - 自身的s(强壮值)，

要使每头牛的危险值最小，这显然是与w 和 s同时相关，

所以猜测出一种做法按 每头牛的w + s进行升序排序

然后依次从小到达 按层数由高到低的顺序来计算每头牛的危险值

#include #include #define x first#define y secondusing 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以上就是对 经典贪心问题 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。

参考文献

https://www.acwing.com/activity/content/19/