[数据结构与算法]LeetCode 101 贪心算法（Assign Cookies（Easy））

贪心算法分配问题

题目描述

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例

输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。

Input: [1,2], [1,2,3]
Output: 2

题解

在这里我们要依据每个孩子的饥饿程度给予大于等于饥饿程度的饼干这样孩子才能吃饱，我们首先要满足饥饿程度最小的孩子再满足饥饿程度大的孩子，所以我们首先要对孩子的饥饿程度进行排序。
而对于一定饥饿程度的孩子，我们要从剩余的饼干中挑选一个合适的，这就要把饼干从小到大与孩子的饥饿程度进行比较。所以饼干的大小也要进行排序。
这就浮现出了我们的思路：先将孩子的饥饿程度和饼干大小进行排序，然后将最小饥饿程度的孩子取出，从饼干中由小到大进行匹配，找到第一个大于等于孩子饥饿程度的饼干。以为孩子的饥饿程度依次增加，所以当匹配到一个饼干后，满足下一个孩子的饥饿程度的饼干必定在刚匹配成功的饼干之后（因为饼干是有序的）。由这样依次遍历完孩子数组或饼干数组满足孩子的饥饿程度就用child++来记录孩子的吃饱数

C++代码如下

int findContentChildren(vector<int>& children,vector<int>& cookies)
{
//把饥饿程度和饼干大小进行排序
sort(children.begin(),children.end());
sort(cookies.begin(),cookies.end());
//定义child和cookie用于循环遍历数组
int child=0,cookie=0;
while (child<children.size()&&cookie<cookies.size())
{
//判断饼干是否满足孩子的饥饿程度，满足就child+1，另外满足的child必定是一个从最左端连续的空间
	if(children[child]<=cookies[cookie]){
		++child;
	}
	++cookie;
}
return child;
}

这些都是作者自己一个一个码的，希望对你有所帮助，如果觉得对你有帮助，请给作者一个大大的赞👍