Leetcode-455的解题过程。

• 题目

  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.
  

  1 2 3 4 5 6 7 8 9 10 11 12 13

  - 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.

• 解析

    给小朋友分饼干，每个小朋友有一个贪婪值表示能满足他的最小饼干大小。简单的贪心算法的应用。基本思路是：将小朋友们按照贪婪值升序排列，随后遍历，从所有饼干中挑一个最小并且能满足他的饼干。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  public class Solution { public int FindContentChildren(int[] g, int[] s) { Array.Sort(g); Array.Sort(s);//饼干也按照大小升序排列 int count = 0; int[] sf = new int[s.Length];//标记数组，1代表没有满足，0代表已经满足 for (int i=0;i<sf.Length;i++){ sf[i]=1; } for (int i=0;i<g.Length;i++){ for (int j=0;j<s.Length;j++){ if (s[j]>=g[i] && sf[j]==1){ count++; sf[j]=0; break; } } } return count; } }