题目链接

455. 分发饼干 - 力扣（LeetCode）

2410. 运动员和训练师的最大匹配数 - 力扣（LeetCode）

题目描述

孩子有n个，g[i]表示n个孩子中第i个孩子胃口值。

饼干有m块，s[j]表示m块饼干中第j块饼干的尺寸。

每个孩子只能吃一块饼干，用来满足自己的胃口(s[j]>=g[i]才可以分给孩子吃)，输入固定的孩子和饼干数组，问可以满足孩子的最大数量。

输入输出样例

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

题目解释

胃口最小的孩子最容易吃饱，优先考虑胃口最小的孩子。

或者优先考虑胃口最大的孩子，但是需要分给他最大的饼干，因为一个孩子只能分给一个孩子，所以不会浪费

官方题解：455. 分发饼干 - 力扣（LeetCode）

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 考虑胃口最大孩子
class Solution {
   public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end(), greater<int>());
        sort(s.begin(), s.end(), greater<int>());

        int childrenIndex = g.size() - 1, cookiesIndex = s.size() - 1;
        int count = 0;

        while (cookiesIndex >= 0 && childrenIndex >= 0) {
            if (s[cookiesIndex--] >= g[childrenIndex]) {
                count++;
                childrenIndex--;
            }
        }

        return count;
    }
};

// 考虑最小胃口孩子
class Solution {
   public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end(), less<int>());
        sort(s.begin(), s.end(), less<int>());
        int childrenIndex = 0, cookiesIndex = 0;
        int count = 0;
        while (cookiesIndex < s.size() && childrenIndex < g.size()) {
            if (s[cookiesIndex++] >= g[childrenIndex]) {
                count++;
                childrenIndex++;
            }
        }
        return count;
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/assign-cookies/solutions/534281/fen-fa-bing-gan-by-leetcode-solution-50se/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
   public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};