做我的世界头像的网站,河南网站建设官网,中企动力这家公司怎么样,如何优化网站推广455.分发饼干
题目#xff1a;
小朋友胃口值数组g[i]#xff0c;饼干尺寸数组 s[j]#xff0c;当饼干尺寸s[j]大于等于g[i]的时候#xff0c;对应小朋友被满足#xff0c;小朋友每一个最多一块饼干 #xff0c;求给定条件下最多被满足的小朋友数量。
思路#xff1a;…455.分发饼干
题目
小朋友胃口值数组g[i]饼干尺寸数组 s[j]当饼干尺寸s[j]大于等于g[i]的时候对应小朋友被满足小朋友每一个最多一块饼干 求给定条件下最多被满足的小朋友数量。
思路
局部最优尺寸最大的饼干先分给胃口最大的小朋友
全局最优然后不断饼干第二大尺寸胃口第二大小朋友不能一次吃饱的不给吃达成全局最优
具体做法就是饼干数组和小孩数组排序然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index s.size() - 1; // 饼干数组的下标int result 0;for (int i g.size() - 1; i 0; i--) { // 遍历胃口if (index 0 s[index] g[i]) { // 遍历饼干result;index--;}}return result;}
}; 如果饼干尺寸大于等于胃口结果1饼干向小尺寸继续遍历胃口向小胃口小孩继续遍历。
如果饼干尺寸小于胃口那么胃口继续向小胃口小孩遍历胃口和饼干都经过排序
也就是从大到小尺寸饼干满足胃口从大到小排序的小孩饼干没满足小孩了就下一个小孩没小孩了就返回结果。
