分发饼干，也要贪心

送饼干，还被馋饼干。但是，每个孩子最多只能得到一个饼干。对于每个孩子i，都有一个食欲值g[i]，它是满足孩子食欲的最小尺寸的饼干；对于每个饼干j，有一个大小s[j]。如果s[j]>=g[i]，我们可以将这个cookiej分配给孩子i，这个孩子就会满意。你的目标是让尽可能多的孩子满意，输出这个最大值。示例1：输入：g=[1,2,3],s=[1,1]输出：1解释：你有三个孩子和两块饼干，三个孩子的食欲值分别为：1,2,3.虽然你有两块小饼干，但是由于它们的大小都是1，你只能满足一个胃口值为1的孩子。所以你应该输出1。例子2：输入：g=[1,2],s=[1,2,3]输出：2解释：你有两个孩子和三块饼干，两个孩子的食欲值分别为1,2。你有足够的饼干，无论是数量还是大小，都能让所有的孩子都满意。所以你应该输出2。提示：1<=g.length<=3*10^40<=s.length<=3*10^41<=g[i],s[j]<=2^31-1idea为了满足更多的孩子，不要造成饼干大小的浪费。大号的饼干既能满足胃口大的孩子，也能满足胃口小的孩子，所以应优先考虑胃口大的孩子。这里的局部最优是给胃口大的人喂大饼干，充分利用饼干的大小喂一个。全局最优是养活尽可能多的孩子。可以尝试使用贪心策略，先对biscuit数组和child数组进行排序。然后从后向前遍历child数组，先用大饼干满足胃口，统计满足的child数量。如图：在分发饼干的例子中，可以看出饼干9只能喂给胃口为7的小朋友，这是整体最优解，想不出反例，所以可以代码。整体C++代码如下：//时间复杂度：O(nlogn)//空间复杂度：O(1)classSolution{public:intfindContentChildren(vector&g,vector&s){sort(g.begin(),g.end());sort(s.begin(),s.end());intindex=s.size()-1;//饼干数组下表intresult=0;for(inti=g.size()-1;i>=0;i--){if(index>=0&&s[index]>=g[i]){result++;index--;}}returnresult;}};从代码中可以看出，我使用了一个索引来控制饼干数组的遍历。饼干的遍历并没有启动for循环，而是使用了自减的方式，这也是一种常用的技巧。有同学看到需要遍历两个数组，就想到用两个for循环，这样逻辑其实很复杂。也可以换个思路，小饼干先喂小胃口。代码如下：end());intindex=0;for(inti=0;i