[R46C]文字编辑器 - 代码源竞赛平台

时空限制

1S/512M

题目描述

你正在开发一个简单的文本编辑器。给定一段包含 $n$ 个单词的文本，按输入顺序依次编号为 $1, 2, \dots, n$，其中第 $i$ 个单词的长度为 $a_i$。

你需要将这些单词按顺序排版，每行最多包含 $m$ 个字符。排版规则如下：

1. 单词必须按输入顺序依次放置，不能改变顺序。
2. 在同一行中，两个相邻的单词之间必须至少有一个空格。
3. 一行中所有单词的长度加上单词之间空格的总长度不能超过 $m$。
4. 如果当前行能够放下当前单词（考虑空格），则必须放在当前行；如果放不下，则该单词必须另起一行作为该行的第一个单词。

请计算排版这段文本最少需要多少行。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示单词的数量和每行最大字符数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个单词的长度。

输出格式

输出一个整数，表示排版这段文本所需的最少行数。

样例

样例输入 #1

5 10
3 4 2 5 2

样例输出 #1

3

样例解释 #1

• 第一行：放置第 $1,2$个单词。总长度为 $3 + 1 + 4 = 8 \le 10$。若再放第 $3$ 个单词，长度变为 $8 + 1 + 2 = 11 > 10$，故第一行放 $2$ 个单词。
• 第二行：放置第 $3,4$ 个单词。总长度为 $2 + 1 + 5 = 8 \le 10$。若再放第 $5$ 个单词，长度变为 $8 + 1 + 2 = 11 > 10$，故第二行放 $2$ 个单词。
• 第三行：放置第 $5$ 个单词。总长度为 $2 \le 10$。 最终共需 $3$ 行。

数据规模

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 10^6$，$1 \le a_i \le m$。