[allocation problem] 455 Distribute cookies

One 、 subject

Suppose you are a great parent , Want to give your kids some cookies . however , Each child can only give one biscuit at most .

For every child i, All have an appetite value g[i], This is the smallest size of biscuit that can satisfy children's appetite ; And every cookie j, They all come in one size s[j] . If s[j] >= g[i], We can put this biscuit j Assign to children i , The child will be satisfied . Your goal is to meet as many children as possible , And output the maximum value .

Example 1:

Input : g = [1,2,3], s = [1,1]
Output : 1
explain :
You have three children and two biscuits ,3 The appetites of a child are ：1,2,3.
Although you have two biscuits , Because they are all of the same size 1, You can only make your appetite worth 1 The children of .
So you should output 1.
Example 2:

Input : g = [1,2], s = [1,2,3]
Output : 2
explain :
You have two children and three biscuits ,2 The appetites of a child are 1,2.
You have enough cookies and sizes to satisfy all children .
So you should output 2.

Two 、 Answer key

The purpose of this problem is that the number of cookies is limited , And to meet more children , The greedy strategy is to give priority to the children with the smallest appetite at each feeding , Only in this way can the final result be greater .

• First , Let's first rank the children according to the degree of hunger .
• then , Start with the first child , That is, the child with the smallest appetite starts to find cookies that can satisfy it , After finding it, start with the next child , Continue searching from the next biscuit , Until all the children have carried out the search operation or the biscuits are exhausted .

3、 ... and 、 Code

int findContentChildren(vector<int> &children,vector<int> &cookies){
    
  sort(children.begin(),children.end());
  sort(cookies.begin(),cookies.end());
  int child=0;
  int cookie=0;
  while(cookie<cookies.size()&&child<children.size()){
    
    if(children[child]<=cookies[cookie]) child++;
    cookies++;
  }
  return child;
}