题目描述
对于给定的一个长度为NN的正整数数列Ai,
现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得满足要求。
输入格式
第1行包含两个正整数N,M表示了数列Ai
的长度与每段和的最大值,第22行包含N个空格隔开的非负整数Ai ,如题目所述。
输出格式
一个正整数,输出最少划分的段数。
输入样例
5 6
4 2 4 5 1
输出样例
3
说明/提示
对于20\%20%的数据,有N≤10N≤10;
对于40\%40%的数据,有N≤1000N≤1000;
对于100\%100%的数据,有N≤100000,M≤10^9N≤100000,M≤10
9,M大于所有数的最小值,Ai 之和不超过10^9
将数列如下划分:
[4][2 4][5 1][4][24][51]
第一段和为44,第22段和为66,第33段和为66均满足和不超过M=6M=6,并可以证明33是最少划分的段数。
算法1
() $O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
int n , m , ans ;
int main ( ) {
cin >> n >> m ;
int sum = 0 ;
for ( int i = 1 ; i <= n ; i ++ ){
int a ;
cin >> a ;
if ( a + sum <= m ) {
sum += a ;
}
else {
ans ++ ;
sum = a ;
}
}
cout << ans + 1 ;
return 0 ;
}