LeetCode Assign Cookies 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.
妈妈要给若干个孩子分饼干，没人一个饼干，不同饼干有不同的大小，同时不同孩子对饼干有一个最小的要求。问怎样分饼干才能满足最多的孩子的要求，求最多满足的孩子的数目。 明显是贪心的思路，把饼干从大到小排序，孩子的要求也从大到小排序，然后我们先尽量用大的饼干满足要求高的孩子，比如你会用一个100大小的饼干满足一个要求为90的孩子，而不是拿这个饼干满足要求为10的孩子，因为要求越低的孩子，被满足的可能性越高。如果当前最大的饼干都不能满足当前的孩子，则当前的策略满足不了这个孩子。 完整代码如下： [cpp] class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = g.size() – 1, j = s.size() – 1, ans = 0; while (i >= 0) { if (j >= 0 && s[j] >= g[i]) { ++ans; –j; } –i; } return ans; } }; [/cpp] 本代码提交AC，用时582MS。为什么会这么慢呀，后来试了下从小到大给孩子分饼干，也就是用能满足当前孩子的最小饼干，其实原理是一样的，尽量不浪费大的饼干： [cpp] class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int i = 0, j = 0, ans = 0; while (i < g.size()) { while (j < s.size() && g[i] > s[j]) { ++j; } if (j >= s.size())break; ++ans; ++i; ++j; } return ans; } }; [/cpp] AC了，但是还是很慢，449MS。。。]]>