LeetCode 455.分发饼干

题目

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

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

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

• 1 <= g.length <= 3 * 10⁴
• 0 <= s.length <= 3 * 10⁴
• 1 <= g[i]，s[j] <= 2³¹ - 1

思路

来不及写了，先放代码，后面补上。

3.21补

采用贪心算法。原始问题可以划分为给每一个孩子分配饼干。而子问题的最优解就是使用最小的饼干满足当前孩子。

int findContentChildren(vector<int>& g, vector<int>& s) 
{
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int l_g = g.size();
        int l_s = s.size();
        int child = 0, cookie = 0;

        while (child < l_g && cookie < l_s)
        {
            if (g[child] <= s[cookie])
            {
                child++;
                cookie++;
            } 
            else
            {
                cookie++;
            }
        }
        return child;
    }

** 注：**

一个经常用到的函数sort()：

// 该函数存在与<algorithm>头文件中，因此在使用该函数前，程序中应包含如下语句：
#include <algorithm>
// 对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
// 按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

参考文章：

C++ sort()排序函数用法详解