← 返回题目列表

AtCoder · awc0097_a

A. 整理书架

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

高桥正在书架上整理书籍。书架上有 N 货架:货架 1,货架 2,……,架子 N,每个架子的宽度为 W 厘米。最初,所有货架都是空的。

有 N 书架上排列的书籍,以及 i第本书 (1 \leq i \leq N) 的厚度为 L_i 厘米。保证每本书的厚度最大为 W,因此每本书都可以单独放在一个书架上。

当 k (k \geq 1) 书籍(厚度 a_1, a_2, \ldots, a_k)从左到右排列在架子上, 使用宽度 该货架的 定义为 (a_1 + a_2 + \cdots + a_k) + (k - 1) 厘米。这对应于总是留下一个 1- 相邻书籍之间的厘米间隙。例如,只有一本书的书架的使用宽度等于该书的厚度,而没有书的书架的使用宽度为 0 厘米。

高桥将书按照从 1-st 书到 N第本书,遵循以下规则。 “当前货架”最初是货架 1。当放置 i第本书:

  1. 如果当前书架上当前没有放置书籍,则将 i从当前书架左端开始的第本书。当前货架不变。
  2. 假设当前书架上已有图书,所用宽度为 S 厘米。
  • If S + 1 + L_i \leq W,放置 i当前书架上已放置书籍右侧的第本书,留下 1- 厘米间隙。当前货架不变。
  • If S + 1 + L_i > W, i第本书不适合当前书架。当前架子之后的架子(编号较大的架子)成为新的“当前架子”。由于架子是按照从最小编号开始的顺序填充的,因此这个新架子总是空的。放置 i从书架左端开始的第本书。

毕竟 N 书籍已排列,确定至少放置一本书的书架总数。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq W \leq 10^9
  • 1 \leq L_i \leq W (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N W
L_1 L_2 \ldots L_N
  • 第一行包含一个整数 N 代表书籍数量和一个整数 W 代表每个架子的宽度,以空格分隔。
  • 第二行包含整数 L_1, L_2, \ldots, L_N 代表每本书的厚度,以空格分隔。

输出

在一行中打印至少放置一本书的书架数量。


示例输入 1

5 10
3 4 2 5 3

示例输出 1

3

示例输入 2

8 15
5 5 5 5 5 5 5 5

示例输出 2

4

示例输入 3

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 3

10