本文共 1473 字，大约阅读时间需要 4 分钟。

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

 

示例 1:

输入: g = [1,2,3], s = [1,1]

输入: g = [1,2], s = [1,2,3]

题解：

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可 以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这 个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到 没有满足条件的饼干存在。简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。 至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。 这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

代码（丑）：

class Solution {public:    int findContentChildren(vector
   
    & g, vector
    
     & s) {        int sum=0;        sort(g.begin(),g.end());        sort(s.begin(),s.end());        for ( int i=0;i
     
      =g[i])                {                    s[j]=0;                    sum++;                    break;                }            }        }        return sum;    }};
     
    
   

优化代码： 

int findContentChildren(vector
   
    & children, vector
    
     & 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;   //只要看能让几个child吃饱就行}
    
   

参考资料：