P5048: 数列分段
传统题
1.000s
时间限制
256MB
内存限制
2 提交
0 解决
【题目描述】
题目描述
对于给定的一个长度为 N 的正整数数列 A，现要将其分成连续的若干段，并且每段和不超过 M（可以等于M ），问最少能将其分成多少段使得满足要求。
输入格式
第一行包含两个正整数 N,M，表示了数列Ai 的长度与每段和的最大值；
第二行包含 N 个空格隔开的非负整数 Ai。
输出格式
输出文件仅包含一个正整数，输出最少划分的段数。
样例
输入
5 6
4 2 4 5 1
输出
3
数据范围与提示
对于 20% 的数据，有N<10；
对于 40% 的数据，有 N≤
1000；
对于 100% 的数据，有 N≤
105，M≤
109 ,M大于所有数的最大值。
【输入】
第一行包含两个正整数 N,M，表示了数列Ai 的长度与每段和的最大值；
第二行包含 N 个空格隔开的非负整数 Ai。
【输出】
输出文件仅包含一个正整数，输出最少划分的段数。