p1182 数列分段 section ii

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，请你将它分成若干段，使得每段的和都不超过 $m$，且段数最少。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示序列 $a$。

输出格式

输出一个整数，表示最少的段数。

数据范围

$1\leq n\leq 10^5$，$1\leq m,a_i\leq 10^4$

输入样例：

5 10
2 3 1 2 4

输出样例：

3

算法1

(贪心) $O(n)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码