分饼干华为机试经典贪心真题Python AC完整代码牛客可直接提交题目描述假设你是一位很棒的家长想要给孩子们分饼干。每个孩子i有一个胃口值g[i]代表这个孩子需要的饼干最小尺寸每块饼干j有尺寸s[j]。如果饼干尺寸s[j] g[i]这个孩子可以得到这块饼干。每个孩子最多只能拿一块饼干每块饼干只能分给一个孩子。求最多能满足多少个孩子。输入描述第一行孩子胃口数组空格分隔第二行饼干尺寸数组空格分隔输入样例1 2 3 1 1输出样例1解释只能满足胃口为1的孩子样例21 2 1 2 3输出2✅贪心思路孩子胃口从小到大排序饼干从小到大排序双指针小饼干优先喂胃口最小的孩子局部最优全局最优如果当前饼干可以满足当前孩子计数1两个指针都后移不满足这块饼干太小看下一块饼干饼干指针后移完整可提交代码importsysdefmain():linessys.stdin.read().splitlines()# 读取孩子胃口数组glist(map(int,lines[0].split()))# 读取饼干数组slist(map(int,lines[1].split()))# 贪心核心两个数组都升序排序g.sort()s.sort()child0# 孩子指针cookie0# 饼干指针count0# 满足的孩子数量whilechildlen(g)andcookielen(s):ifs[cookie]g[child]:# 当前饼干可以满足这个孩子count1child1cookie1else:# 饼干太小看下一块饼干cookie1print(count)if__name____main__:main()机试重点笔记核心策略两个数组都升序小饼干优先喂胃口最小的边界情况测试时一定要想到没有孩子 / 没有饼干输出0所有饼干都太小满足不了任何人输出0饼干数量远多于孩子贪心适用原因优先消耗最小能满足的饼干把大饼干留给胃口更大的孩子不会浪费大饼干做题模板提取可以背g.sort()s.sort()c1c2ans0whilec1len(g)andc2len(s):ifs[c2]g[c1]:ans1c11c21else:c21print(ans)对比区分分饼干双数组排序 双指针贪心活动选择单数组按结束时间排序贪心区间合并区间数组按起点排序贪心