数列分段

题目描述

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

输入

第 1 行包含两个正整数 N，M，表示了数列 A[i]的长度与每段和的最大值，第 2 行包含 N 个空格隔开的非负整数 A[i]，如题目所述。

输出

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

样例输入

5 6

4 2 4 5

样例输出

提示

【数据规模与约定】

对于 20%的数据，有 N<=10；

对于 40%的数据，有 N<=1000；

对于 100%的数据，有 N<=100000，M<=109，M 大于所有数的最小值，A[i]之和不超过 109。

【样例说明】

将数列如下划分：

[4][2 4][5 1]

第一段和为 4，第 2 段和为 6，第 3 段和为 6 均满足和不超过 M=6，并可以证明 3 是最少划分的段数。

这绝对是一道贪心水题，想绕道就绕吧。

但即使是一道水题，我也要说说。

题中说的是要最少的划分段数，那就是让每一段的数字尽可能的多。所以我们只要从头开始遍历，一直加，直到和大于 M，就说明这一段的数最多了。

能支持这种想法是因为有这句话：正整数数列 A[i]。因为如果有负数的话，累加的值就不能保证一直递增，上述算法就不成立了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 #define rep(i, a, n) for(int i = a; i <= n; ++i)
 8 #define per(i, n, a) for(int i = n; i >= a; --i)
 9 typedef long long ll;
10 const int maxn = 1e5 + 5;
11 int a[maxn], n, m;
12 int sum = 0, ans = 1;
13 int main()
14 {
15     freopen("divide_a.in", "r", stdin);
16     freopen("divide_a.out", "w", stdout);
17     scanf("%d%d", &n, &m);
18     rep(i, 1, n) scanf("%d", &a[i]);
19     rep(i, 1, n)
20     {
21         if(sum + a[i] > m) {ans++; sum = a[i];}
22         else sum += a[i];
23     }
24     printf("%d
", ans);
25     return 0;
26 }