3169：【例28.3】 数列分段

【题目描述】

对于给定的一个长度为 nn 的正整数数列aiai，现要将其分成连续的若干段，并且每段和不超过 mm（可以等于 mm），问最少能将其分成多少段使得满足要求。

【输入】

第一行包含两个正整数 nn,mm，表示了数列的长度与每段和的最值。

第二行包含nn个空格隔开的非负整数aiai。

数据范围：1≤n≤1051≤n≤105,1≤ai≤m≤1041≤ai≤m≤104。

【输出】

输一个正整数，输出最少划分的段数。

【输入样例】

5 6

4 2 4 5 1

【输出样例】

3

源代码：

#include

using namespace std;

const int maxn=100010;

int c[maxn];

int main()

{

int n,m,Count;

Count=1;

scanf("%d %d",&n,&m);

for(int i=0;i

scanf("%d",&c[i]);

}

int tmp=0;//阶段和

for(int i=0;i

tmp+=c[i];

if(tmp>m){

Count++;

tmp=0;

tmp+=c[i];

}

}

printf("%d\n",Count);

return 0;

}