【例28.3】 数列分段

解题思路

正整数段贪心：当前段只要还能加入下一个数就加入；若加入会超过 m，则从该数开新段。

正确性说明

任意合法第一段不能比贪心第一段更长，否则和会超限。把某最优方案的第一段延长到贪心边界不会增加剩余所需段数；对余下序列归纳，贪心段数最少。

易错点

等于 m 可以继续属于当前段；每个 a_i 保证不超过 m。

复杂度

时间 O(n)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int segments = 1, sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (sum + x > m) {
            segments++;
            sum = x;
        } else
            sum += x;
    }
    cout << segments << "\n";
    return 0;
}