题目描述
对于给定的一个长度为\(N\)的正整数数列\(A_i\)，现要将其分成连续的若干段，并且每段和不超过\(M\)（可以等于\(M\)），问最少能将其分成多少段使得满足要求。
分析
简单思考一下，首先这是一段连续的区间，所以一般是不能使用sort。
如果要考虑贪心的话，我们只能采取最简单的方法，也就是每一段求一下，用一个tmp扫一下，如果可以将当前的数加入tmp中，那么就加进去，不行的话重新开一段区间。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m;
int a[maxn];
inline int read(){int w=0,X=0;char ch=0;while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}while (isdigit(ch)) {X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}return w?-X:X;
}
int main(){n=read(),m=read();for (int i=1;i<=n;i++) a[i]=read();int ans=0,tmp=0;for (int i=1;i<=n;i++) {if (tmp+a[i]>m) tmp=0,ans++;tmp+=a[i];}if (tmp) ans++;printf("%d\n",ans);return 0;
}