题目描述
有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子可以吃饱。求解最多有多少孩子可以吃饱。
输入输出样例
输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。
Input: nums = [1,2],[1,2,3]
Output: 5
在这个样例中，我们可以给两个孩子喂[1,2],[1,3],[2,3]这三种组合的任意一种。 # 题解 因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量便利剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的，且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。 简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饮腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少组合可以满足条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int findContentChildren(vector<int>& children, vector<int>& cookies) {
sort(children.begin(),children.end());
sort(cookies.begin(),cookies.end());
int child = 0,cookie = 0;
while (child < children.size() && cookie < cookies.size()) {
if (children[child] <= cookies[cookie]) ++child;
++cookie;
}
return child;
}
};
|