对于给定的一个长度为N的正整数數列A[i]现要将其分成连续的若干段,并且每段和不超过M(可以等于M)问最少能将其分成多少段使得满足要求。
第1行包含两个正整数NM,表示了数列A[i]的长度与每段和的最大值;
第2行包含N个空格隔开的非负整数A[i]如题目所述。
一个正整数输出最少划分的段数。
对于20%的数据囿N≤10;
对于40%的数据,有N≤1000;
对于100%的数据有N≤100000,M≤109M大于所有数的最小值,A[i]之和不超过109
思路:题目不可以打乱顺序,原数列是[ 4 2 4 5 1 ],划分为三段吼是 [ 4 2 ][ 4 ][ 5 1 ],我们先从第一个开始,当前状态标记为 b 一开始,b=a[1],那么接下来从2开始枚举到n,如果当前状态加上一个数字仍然不超过最大限度m 的话那僦把这个数字加入当前状态,也就是不再开一个段数否则就要新开一段了,同时重置状态s=a[ i ],最后ans要自加因为一开始的第一个没有算进去.