分数: 266 分
问题陈述
高桥正在进行一项利用雨水收集雨水的实验 N 水桶。桶的编号从 1 to N和桶 i 容量为 C_i 升。最初,所有桶都是空的。
水桶连接成一条线,水流如下。高桥连续倒了总共 W 升水放入桶中 1。流入水桶的水 i (1 \leq i \leq N-1) 积聚在桶中 i 直到到达桶 i的容量 C_i。后斗 i 已满(恰好 C_i 升水已累积),流入水桶的任何额外水 i 将全部流入桶中 i+1。后斗 N 满了,任何额外流入的水都会溢出并消失。
确定倒完所有水后装满的桶的数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W \leq 10^{18}
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N W C_1 C_2 \cdots C_N
- 第一行包含一个整数 N 代表桶的数量和一个整数 W 代表要倒入的水总量(以升为单位),以空格分隔。
- 第二行包含整数 C_1, C_2, \ldots, C_N 代表每个桶的容量,以空格分隔。
- C_i 代表桶的容量(单位为升) i.
输出
在一行中打印已满的桶的数量。
示例输入 1
3 10 3 4 5
示例输出 1
2
示例输入 2
5 25 5 10 3 8 6
示例输出 2
3
示例输入 3
6 1000000000000000000 100000000 200000000 300000000 400000000 500000000 600000000
示例输出 3
6