Leetcode 455. Assign Cookies(分曲奇)

题意重述

每个孩子有他们期望得到曲奇的大小,这个值记为gi(贪婪因子),而你手中每个曲奇大小记为sj,现在你要使尽可能满足更多的孩子 原题链接

解题思路

贪婪算法的典型例题,分配遵循如下原则:
1. 如果一个孩子对所有的曲奇大小都满足,那就分给他最小的
2. 如果一个曲奇满足所有孩子的需求,那就把它分给期望得到最大的那个孩子

将gi和sj两个数组从小到大排序后一一比较,若满足则游标同时加一,若不满足则只有sj游标加一(尝试用较大的去满足)

代码示例:
/*
Assume(假设) you are an awesome parent and want to give your children some cookies. 
But, you should give each child at most one cookie(每个孩子至多一个曲奇). 
Each child i has a greed factor gi(贪婪因子), 
which is the minimum size of a cookie that the child will be content with(孩子被满足的最小曲奇尺寸); 
and each cookie j has a size sj. 
If sj >= gi, we can assign the cookie j to the child i, and the child i will be content.
Your goal is to maximize the number of your content children(尽力满足更多的孩纸) and output the maximum number.

Note:
You may assume the greed factor is always positive. 
You cannot assign more than one cookie to one child.

Example 1:
Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.
*/

#include<bits/stdc++.h>
using namespace std;

class Solution
{
    public:
        int findContentChildren(std::vector<int>& g, std::vector<int>& s) 
        {
            std::sort(g.begin(), g.end());
            std::sort(s.begin(), s.end());
            int child=0;
            int cookie = 0;
            while((child<g.size())&&((cookie<s.size())))
            {
                if(g[child]<=s[cookie])
                {
                    child++;
                }
                cookie++;
            }
            return child;
        }
};

int main()
{
    Solution solution;
    std::vector<int> g;
    std::vector<int> s;

    g.push_back(5);
    g.push_back(10);
    g.push_back(2);
    g.push_back(9);
    g.push_back(15);
    g.push_back(9);

    s.push_back(6);
    s.push_back(1);
    s.push_back(20);
    s.push_back(3);
    s.push_back(8);

    int count = 0;
    count = solution.findContentChildren(g, s);
    cout<<count<<" children has been satisfied!"<<endl;

    return 0;
}    
示例输出
3 children has been satisfied!

发表评论

电子邮件地址不会被公开。 必填项已用*标注