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

数列分段

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

题目描述

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



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

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

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

    分享给朋友:
    返回列表

    上一篇:线段

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

    相关文章

    【题解】光荣的梦想

    【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平...

    【题解】大数取模

    【题目描述】求m%n。【输入描述】两个数,m和n。【输出描述】m模n的值。【样例输入】3【样例输出】2【数据范围】对于30%的数据, 1<m<10^18对于70%的数据, m>10^...

    【题解】赢得比赛需要的最少训练时长

    【题目描述】你正在参加一场比赛,给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力...

    【题解】画百钱买百鸡

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

    剪刀石头布

    【题目描述】石头剪子布,是一种猜拳游戏。起源于中国,然后传到日本、朝鲜等地,随着亚欧贸易的不断发展它传到了欧洲,到了近现代逐渐风靡世界。简单明了的规则,使得石头剪子布没有任何规则漏洞可钻,单次玩法比拼...

    【题解】飞奔的马

    【题目描述】农场里的马,在草场开心地吃着牧草,直到天色晚了,牧马的人会将马依次按号牌大小,依次放入相应的位置。但是这马总是打乱了顺序,于是牧马人都会想办法把这些马都排好:每次从最前面开始,然后与后面的...