#3734. 分糖果
分糖果
题目描述
有 个小朋友排成一排,第 个小朋友想要 颗糖果。老师手里一共有 颗糖果。
老师按顺序从第 个小朋友走到第 个小朋友,对于每个小朋友:如果剩下的糖果数量不少于他想要的糖果数,就满足他;否则跳过这个小朋友,继续看下一个。
请计算老师最多能满足多少个小朋友。
输入格式
第一行两个整数 和 ,分别表示小朋友数量和糖果总数。 第二行 个整数 ,表示每个小朋友想要的糖果数。
输出格式
输出一个整数,表示最多能满足的小朋友数量。
样例
3 10
4 5 3
2
4 12
3 8 2 1
3
说明/提示
对于 的数据,,,。
样例说明
样例 1:老师有 颗糖果。第 1 个小朋友要 颗,剩余 颗;第 2 个小朋友要 颗,剩余 颗;第 3 个小朋友要 颗,不够,跳过。最终满足 个小朋友。
样例 2:老师有 颗糖果。第 1 个小朋友要 颗,剩余 颗;第 2 个小朋友要 颗,剩余 颗;第 3 个小朋友要 颗,不够,跳过��第 4 个小朋友要 颗,剩余 颗。最终满足 个小朋友。
解析
解题思路
题目描述的是一个按顺序贪心的过程:老师从第 1 个小朋友走到第 n 个小朋友,如果当前剩余糖果数 m 不少于该小朋友想要的 a_i,就满足他并扣除相应糖果;否则跳过,继续检查下一个小朋友。
由于老师必须按顺序处理,且一旦能买就必须买(题面规定“如果剩下的糖果数量不少于他想要的糖果数,就满足他”),所以整个过程是确定的,不需要做任何决策。我们只需按照题面模拟一遍:维护剩余糖果数 m 和已满足人数 ans,依次读入每个 a_i,若 m >= a_i 则 m -= a_i、ans++;否则不处理。
算法选择理由
本题没有选择空间——老师的策略已被题面固定,因此直接模拟就是正确做法。不能通过排���或重新排列来增加人数,因为顺序不可改变。贪心在这里不是“选择最优”,而是“忠实执行规则”。
复杂度分析
- 时间复杂度:,每个小朋友只处理一次。
- 空间复杂度:,只需常数个变量(边读边处理,无需存储数组)。
对于 、 的数据规模,该做法远低于 1 秒限制,完全足够。
来源
AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心