【算法训练营】贪心算法专题(一)

03-10 阅读 0评论

🕺作者：主页

$【算法训练营】贪心算法专题(一),【算法训练营】贪心算法专题(一),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第1张$

（图片来源网络，侵删）

我的专栏
C语言从0到1
探秘C++
数据结构从0到1
探秘Linux
菜鸟刷题集

😘欢迎关注：👍点赞🙌收藏✍️留言

🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

前言

这篇都是关于贪心算法的OJ题，但是并不只有这一种方法，但在本篇中只写出贪心的解法，标题下面都有超链接，可以同时过去写题哦~

之后还会更新相关专题的，敬请期待！！

算法解释

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。

$【算法训练营】贪心算法专题(一),【算法训练营】贪心算法专题(一),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$

（图片来源网络，侵删）

举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

📍455. 分发饼干

链接：455. 分发饼干

解题思路

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。

简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。

至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

$【算法训练营】贪心算法专题(一),【算法训练营】贪心算法专题(一),词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第4张$

（图片来源网络，侵删）

注意：对数组或字符串排序是常见的操作，方便之后的大小比较。

注意：在之后的讲解中，若我们谈论的是对连续空间的变量进行操作，我们并不会明确区分数组和字符串，因为它们本质上都是在连续空间上的有序变量集合。一个字符串“abc”可以被看作一个数组 [‘a’,‘b’,‘c’]。

AC代码

class Solution {
public:
    int findContentChildren(vector& g, vector& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int child=0,cookie=0;
        while(child
            if(g[child] 
public:
    int eraseOverlapIntervals(vector
        sort(intervals.begin(), intervals.end(), [](vector
            return a[1]