#3734. 分糖果

分糖果

题目描述

有 nn 个小朋友排成一排,第 ii 个小朋友想要 aia_i 颗糖果。老师手里一共有 mm 颗糖果。

老师按顺序从第 11 个小朋友走到第 nn 个小朋友,对于每个小朋友:如果剩下的糖果数量不少于他想要的糖果数,就满足他;否则跳过这个小朋友,继续看下一个。

请计算老师最多能满足多少个小朋友。

输入格式

第一行两个整数 nn 和 mm,分别表示小朋友数量和糖果总数。 第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n,表示每个小朋友想要的糖果数。

输出格式

输出一个整数,表示最多能满足的小朋友数量。

样例

3 10
4 5 3
2 
4 12
3 8 2 1
3 

说明/提示

对于 100%100\% 的数据,1≤n≤1001\le n\le 100,0≤m≤1040\le m\le 10^4,0≤ai≤1040\le a_i\le 10^4。

样例说明

样例 1:老师有 1010 颗糖果。第 1 个小朋友要 44 颗,剩余 66 颗;第 2 个小朋友要 55 颗,剩余 11 颗;第 3 个小朋友要 33 颗,不够,跳过。最终满足 22 个小朋友。

样例 2:老师有 1212 颗糖果。第 1 个小朋友要 33 颗,剩余 99 颗;第 2 个小朋友要 88 颗,剩余 11 颗;第 3 个小朋友要 22 颗,不够,跳过��第 4 个小朋友要 11 颗,剩余 00 颗。最终满足 33 个小朋友。

解析

解题思路

题目描述的是一个按顺序贪心的过程:老师从第 1 个小朋友走到第 n 个小朋友,如果当前剩余糖果数 m 不少于该小朋友想要的 a_i,就满足他并扣除相应糖果;否则跳过,继续检查下一个小朋友。

由于老师必须按顺序处理,且一旦能买就必须买(题面规定“如果剩下的糖果数量不少于他想要的糖果数,就满足他”),所以整个过程是确定的,不需要做任何决策。我们只需按照题面模拟一遍:维护剩余糖果数 m 和已满足人数 ans,依次读入每个 a_i,若 m >= a_i 则 m -= a_i、ans++;否则不处理。

算法选择理由

本题没有选择空间——老师的策略已被题面固定,因此直接模拟就是正确做法。不能通过排���或重新排列来增加人数,因为顺序不可改变。贪心在这里不是“选择最优”,而是“忠实执行规则”。

复杂度分析

  • 时间复杂度:O(n)O(n),每个小朋友只处理一次。
  • 空间复杂度:O(1)O(1),只需常数个变量(边读边处理,无需存储数组)。

对于 n≤100n \le 100、m≤104m \le 10^4 的数据规模,该做法远低于 1 秒限制,完全足够。

来源

AI 生成 · 云端大模型(域):deepseek-chat · 普及- · 贪心