455. Assign Cookies (Easy)

題目描述

有一群孩子和一堆餅干，每個(gè)孩子有一個(gè)饑餓度，每個(gè)餅干都有一個(gè)大小。每個(gè)孩子只能吃
最多一個(gè)餅干，且只有餅干的大小大于孩子的饑餓度時(shí)，這個(gè)孩子才能吃飽。求解最多有多少孩
子可以吃飽。
輸入輸出樣例
輸入兩個(gè)數(shù)組，分別代表孩子的饑餓度和餅干的大小。輸出最多有多少孩子可以吃飽的數(shù)
量。

Input: [1,2], [1,2,3]
Output: 2

在這個(gè)樣例中，我們可以給兩個(gè)孩子喂 [1,2]、[1,3]、[2,3] 這三種組合的任意一種。

題解

因?yàn)轲囸I度最小的孩子最容易吃飽，所以我們先考慮這個(gè)孩子。為了盡量使得剩下的餅干可以滿足饑餓度更大的孩子，所以我們應(yīng)該把大于等于這個(gè)孩子饑餓度的、且大小最小的餅干給這個(gè)孩子。滿足了這個(gè)孩子之后，我們采取同樣的策略，考慮剩下孩子里饑餓度最小的孩子，直到?jīng)]有滿足條件的餅干存在。

簡(jiǎn)而言之，這里的貪心策略是，給剩余孩子里最小饑餓度的孩子分配最小的能飽腹的餅干。

至于具體實(shí)現(xiàn)，因?yàn)槲覀冃枰@得大小關(guān)系，一個(gè)便捷的方法就是把孩子和餅干分別排序。
這樣我們就可以從饑餓度最小的孩子和大小最小的餅干出發(fā)，計(jì)算有多少個(gè)對(duì)子可以滿足條件。

注意

• 對(duì)數(shù)組或字符串排序是常見(jiàn)的操作，方便之后的大小比較。
  
• 在之后的講解中，若我們談?wù)摰氖菍?duì)連續(xù)空間的變量進(jìn)行操作，我們并不會(huì)明確區(qū)分?jǐn)?shù)組
  和字符串，因?yàn)樗麄儽举|(zhì)上都是在連續(xù)空間上的有序變量集合。一個(gè)字符串“abc”可以被看作一個(gè)數(shù)組 ['a’,'b’,'c’]。

代碼

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int child=0,cookie=0;
        while(child<g.size()&&cookie<s.size())
        {
            // 如果當(dāng)前胃口最小的孩子 小于等于最小尺寸的餅干  child++  變成下一個(gè)孩子
            // 如果當(dāng)前胃口最小的孩子 大于 最小尺寸的餅干 孩子不+1  餅干+1
            if(g[child]<= s[cookie])
                child++;
            cookie++;
        }
        return child;
    }
};