leetcode 455.分发饼干

思路：贪心思路

其实对于这个题目的第一眼就是最优子问题推到最优。

我们试想，怎么样才能最大限度地满足孩子的需求呢？那当然是每块饼干都能正好或者差距小的满足孩子的胃口。也就是说，尺寸小的饼干满足胃口小的，尺寸大的饼干满足胃口大的。所以，我们会想到对于这两个数组进行排序操作。

OK，那么我们排序之后，还需要有一个问题：也就是说，当我们分完一个饼干了，同时我们也分完给一个孩子了，需要标志出他们的状态如何才行。也就是分完饼干我们需要标注一个已经分配完的标志状态，这里就定义了一个st数组。

注意：为什么内循环里面需要用break？这里的程序是对每个饼干选择孩子进行操作的，所以我们需要遍历孩子，然后标志孩子的状态。但是饼干呢？我们为了节省空间，就用了break，结束对于这个饼干的遍历，也就是防止它给完一个小朋友之后再次分发，省时省空间。

上代码：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(),s.end());
        sort(g.begin(),g.end());
        int count=0;
        vector<int>st(g.size()+1,0);
        for(int i=0;i<s.size();i++){
            for(int j=0;j<g.size();j++){
                if(s[i]>=g[j]&&!st[j]){
                    st[j]=1;
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};