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

数列分段

亿万年的星光1年前 (2025-03-14)题解目录1057

题目描述

对于给定的一个长度为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



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

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

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

    分享给朋友:
    返回列表

    上一篇:线段

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

    相关文章

    【题解】增添战斗力

    【题目描述】大战即将来临,杰洛特需要为自己增添战斗力,广袤的大陆有诸多豪杰,正好可以为杰洛特所用    杰洛特分别有两处地方n1,n2需要豪杰的战斗力    一...

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

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

    【题解】阳光

    【题目描述】给出一个n*n的矩阵,矩阵每个元素数值代表这个位置的阳光情况,给出正整数k,需要我们求出哪一处的k*k 区域的阳光平均值最多,阳光平均值为k*k 区域的阳光总和除于k*k。蒜头君想让我们输...

    2021年市南区程序设计竞赛(小学组)

    1.建设病房(build.cpp)【题目描述】2020年1月23日下午,武汉市建设局紧急召集中建三局等单位举行专题会议,要求参照2003年抗击非典期间北京小汤山医院模式,在武汉职工疗养院建设火神山医院...

    【题解】区间和

    【描述】输入一个整数Q,进行Q次询问,每次给定两个整数l和r,每一次输出l~r中所有平方数的和 % 1000000007【输入】第一行是一个整数Q后面的Q行每行有2个数字l和r【输出】Q行,...

    2021年市北区程序设计竞赛题(⼩学组)

    最⼤值的相乘(maxx.cpp)【问题描述】第⼀⾏有x个正整数a1,a2,..,ax,第⼆⾏有y个正整数b1,b2,...,by,第三⾏有z个正整数c1,c2,...,cz,假设第⼀⾏的x个正整数中的...