对于给定的一个长度为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≤10^9\),M大于所有数的最小值,\(A_i\)之和不超过\(10^9\)。
将数列如下划分:
[4][24][51]
第一段和为4,第2段和为6,第3段和为6均满足和不超过M=6,并可以证明3是最少划分的段数。
#include <iostream>
using namespace std;
int main() {
int n,m,i,t=0,ans=1;
cin>>n>>m;
int a[n];
for(i=0;i<n;++i)
cin>>a[i];
for(i=0;i<n;++i) {
t+=a[i];
if(t>m) {
++ans;
t=a[i];
}
}
cout<<ans<<endl;
return 0;
}
原文:https://www.cnblogs.com/yuzec/p/12829393.html