455.分发饼干【分配问题】

455.分发饼干【分配问题】

题目

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

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

示例1

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

在这里插入图片描述

示例2

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

在这里插入图片描述

题解

胃口值 g[i] 最小的孩子最容易吃饱，所以我们先考虑最容易吃饱的孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。我们只需要将孩子按照胃口值从小到大排列，将饼干按照尺寸从小到大排列，每次找到胃口值最小的孩子，并将最小的能满足这个孩子的饼干分配给他即可。

举例

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

请添加图片描述

① 首先我们按照 胃口值 和 尺寸 分别对孩子和饼干排序

请添加图片描述

② 我们令 child = 1来选中第一个孩子，也就是 胃口值 最小的孩子。令 cookie = 1来选中第一块饼干，也就是 尺寸 最小的饼干。 第一块饼干的尺寸为 1 ，满足第一个孩子，所以 ++child，++cookie 我们下一次应该选中第二个孩子，选中第二块饼干。

请添加图片描述

③ 此时 child = 2，cookie = 2 ，选中第二个孩子，第二块饼干。第二块饼干不满足第二个孩子，所以 ++cookie，饼干选择第三块饼干，孩子仍是第二个孩子。

请添加图片描述

④ 此时 child = 2，cookie = 3 ，选中第二个孩子，第三块饼干。第三块饼干满足第二个孩子，所以 ++child，++cookie，下一次选择第三个孩子，第四块饼干。

请添加图片描述

⑤ 此时 child = 3，cookie = 4 ，选中第三个孩子，第四块饼干。第四块饼干满足第三个孩子，所以 ++child，++cookie，下一次选择第四个孩子，第五块饼干。

请添加图片描述

⑥ 此时 child = 4，cookie = 5 ，选中第四个孩子，第五块饼干。第五块饼干满足第四个孩子，所以 ++child，++cookie，下一次选择第五个孩子，第六块饼干。

请添加图片描述

⑦ 此时 child = 5，cookie = 6 ，选中第五个孩子，第六块饼干。第六块饼干满足第五个孩子，所以 ++child，++cookie，此时 child = 6，cookie = 7。 当 child > children.size() 或 cookie>cookies.size() 即 即child > 所有孩子的个数 或 cookie > 所有饼干的个数，终止循环，双方都不满足分配的条件了。循环终止。

请添加图片描述

代码

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; //++count
            ++cookie;
        }
        return child;
    }
};

查看上述题解，每一步都有 ++ cookie，我们可以把 ++ cookie放到判断条件外。很多同学可能会想另设一个 count 变量计数，但 每次 ++ child 的条件和 ++count条件一样，我们可以省去 ++ count，把 child 作为返回值即可。