#3736. 分糖果
分糖果
题目描述
有 个小朋友排成一排,第 个小朋友想要 颗糖果。老师手中有 颗糖果,按顺序从第 个小朋友开始发放,每个小朋友要么满足(发给他恰好 颗),要么跳过(一颗也不发)。若剩余糖果不足以满足当前小朋友,则只能跳过。
老师希望被满足的小朋友数量尽可能多。请计算最多能满足多少个小朋友。
注意:小朋友必须按编号顺序依次处理,不能回头补发。
输入格式
第一行两个整数 ,分别表示小朋友数量和糖果总数。 第二行 个整数 ,表示每个小朋友想要的糖果数。
输出格式
输出一个整数,表示最多能满足的小朋友数量。
样例
3 10
6 5 4
2
5 15
3 8 5 2 2
4
说明/提示
数据范围
样例说明
样例 1:糖果共 颗。第 1 个要 颗,满足后剩 颗;第 2 个要 颗,不够,跳过;第 3 个要 颗,满足后剩 颗。共满足 个。
样例 2:糖果共 颗。依次处理:要 颗满足(剩 );要 颗满足(剩 );要 颗不够跳过;要 颗满足(剩 );要 颗满足(剩 )。共满足 个。
解析
解题思路
题目要求按编号顺序处理每个小朋友,每个小朋友只能选择“满足”或“跳过”,并且一旦剩余糖果不足就只能跳过。目标是让被满足的人数最多。
由于处理顺序固定,且每个小朋友的代价都是正的,因此可以采用贪心:只要当前剩余糖果足够满足当前小朋友,就直接满足他。直观上,早点满足当前小朋友只会减少剩余糖果,但不会影响前面已经做出的选择;若当前能选却跳过,把糖果留给后面,最多也只能换来同样数量的人,而且后面的孩子可能需求更大,反而不会更优。
更形式化地看,对于固定顺序,任何最优方案中,如果某个位置能够满足却没有满足,那么把“满足”提前到当前位置不会使答案变差,因为总消耗不变或更少,且顺序约束仍然满足。因此“能选就选”的贪心策略最优。
算法选择理由
本题 ,,数据规模很小,甚至可以用动态规划。但由于顺序固定且每个物品价值相同(都是让答案加一),贪心显然更简单且正确。
复杂度分析
只需从左到右扫描一遍数组,时间复杂度为 ,空间复杂度为 (存储输入数组;也可优化为 )。
参考代码要点
维护剩余糖果数 m,遍历每个小朋友:若 m >= a[i],则满足并令 m -= a[i]、答案加一;否则跳过。最终输出答案即可。
来源
AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心