当前位置:首页 > 题解目录 > 正文内容

数列分段

亿万年的星光10个月前 (03-14)题解目录769

题目描述

对于给定的一个长度为N的正整数数列A[i],现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得满足要求。

输入格式

第1行包含两个正整数N,M,表示了数列A[i]的长度与每段和的最大值;

第2行包含N个空格隔开的非负整数A[i],如题目所述。

输出格式

一个正整数,输出最少划分的段数。

样例输入

5 6 
4 2 4 5 1

样例输出

3

提示

【数据范围】

对于20%的数据,有N≤10

对于40%的数据,有N≤1000

对于100%的数据,有N≤100000,M≤109M大于所有数的最小值,A[i]之和不超过109



本篇文章已加密,请输入密码后查看。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:线段

下一篇:【题解】流感传染

相关文章

单词提取

【题目描述】毛毛是个粗心的孩子,有一天在写英语作文时,不小心把不属于英文的字符混了进去。现在请帮他筛选出正常的英语单词。【输入描述】一行英语句子,大小写不定。以英文句点结尾。【输出描述】 删...

【题解】画百钱买百鸡

【题目描述】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡。问鸡翁、鸡母、鸡雏各几何?#include<iostream> using namespace ...

【题解】密码截获

【题目描述】Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码 进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。...

【题解】Best Cow Fences

【题目描述】    给定一个长度为n的正整数序列A。求一个平均数最大的,长度不小于L的子序列。【输入描述】第一行,n和L;n个正整数,表示A。【输出描述】&nb...

【题解】取余(2019青岛市程序设计竞赛)

【问题描述】给你n个正整数a1,a2,..,an。求(a1*a2*..an)%10007的值。【输入】第一行,n,表示整数的个数。第二行,n个用空格隔开的正整数。【输出】一个整数,(a1*a2*..a...

【题解】采摘花生2

【题目描述】Hello Kitty又一次来到花生地里摘花生,从左上角进入花生地,从右下角出去,只能向右或者向下,请问Hello Kitty应该沿着什么样的路线走,能够摘到的花生数量最多(假设花生地里没...