对于给定的一个长度为NN的正整数数列A_i，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。
第1行包含两个正整数N,M，表示了数列A_i?的长度与每段和的最大值，第2行包含N个空格隔开的非负整数A_i?，如题目所述。
一个正整数，输出最少划分的段数。
分析：这个题也是标准的贪心问题，每个区段的合并只与当前有关，与前后都无关，显然贪心策略是让一个数字能尽可能的合并更多的数字。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define maxn 100005 using namespace std; int a[maxn],ans,n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { int sum=0,j; ans++; for(j=i;j<=n;j++) { if(sum+a[j]>m) break; else sum+=a[j]; } i=j-1; } printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/Hoyoak/p/11345737.html
