Leetcode455、孩子分糖果

贪心规律

需求因子数组 g = [2, 5, 9, 9, 10, 15];糖果大小数组 s = [1, 3, 6, 8, 20]。 核心目标:让更多孩子得到满足，有如下规律:

1.某个糖果如果不能满足某个孩子，则该糖果也一定不能满足需求因子更大的孩子。 如，
糖果1(s = 1)不能满足孩子1(g = 2)，则不能满足孩子2、孩子3、...、孩子7;
糖果2(s = 3)不能满足孩子2(g = 5)，则不能满足孩子3、孩子4、...、孩子7;
...

2.某个孩子可以用更小的糖果满足，则没必要用更大糖果满足，因为可以保留更大的糖果
满足需求因子更大的孩子。(贪心!) 如，
孩子1(g = 2)，可以被糖果2(s = 3)满足，则没必要用糖果3、糖果4、糖果5满足; 孩子2(g = 5)，可以被糖果3(s = 6)满足，则没必要用糖果4、糖果5满足;
...

3.孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，用某个糖果 满足一个较大需求因子的孩子或满足一个较小需求因子的孩子效果是一样的(最终满足的总量 不变)。(贪心!)

思路

代码

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int findContentChildren(vector<int>& g, vector<int>& s)
    {
        // 对两个数组排序
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0;  // g index
        int j = 0;  // s index
        while (i < g.size() && j < s.size())
        {
            if (g[i] <= s[j])
                i ++;
            j ++;
        }
        return i;
    }
};

int main()
{
    Solution S;

    vector<int> g;
    vector<int> s;
    int child[] = {2, 5, 9, 9, 10, 15};
    int cookie[] = {1, 3, 6, 8, 20};

    for (int i = 0; i < 6; i++)
    {
        g.push_back(child[i]);
    }

    for (int i = 0; i < 5; i++)
    {
        s.push_back(cookie[i]);
    }

    int res = S.findContentChildren(g, s);
    cout << res << endl;
    return 0;
}