这是一道入门级的贪心算法题,这道题的关键有两点:
1.首先需要对孩子的胃口大小,饼干大小进行排序
2.小尺寸的饼干用来满足小胃口的孩子,大尺寸的饼干用来满足大胃口的孩子,用这样的策略分发饼干。
如果用大尺寸的饼干去满足小胃口的孩子,那么大胃口的孩子可能得不到满足,浪费了机会。
代码:
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());//对孩子的胃口值进行排序sort(s.begin(), s.end());//对饼干大小进行排序int i = 0;for(int x : s){if(i < g.size() && g[i] <= x)//x可以满足第i个孩子i++;}return i;}
};