「一本通 1.1 练习 2」数列分段

GitHub跳转原题关系图返回列表

按原序列顺序贪心累加，当前段和超过上限时另起一段，单次线性扫描求得最少分段数。

OJ: roj

题目 ID: 1428

难度:入门

标签:贪心

创建: 2026-09-30 09:43

更新: 2026-10-05 23:30

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

给定长度为 NN 的非负整数数列 AiA_i 和正整数 MM，把它分成若干个连续段，使每段之和不超过 MM（可以等于 MM），求最少段数。输入第一行是 N,MN, M，第二行是 NN 个非负整数 AiA_i；输出一个正整数，即最少划分段数。数据范围：N⩽100000N \leqslant 100000，M⩽109M \leqslant 10^9，MM 大于所有数的最小值，AiA_i 之和不超过 10910^9。样例：输入 N=5,M=6N=5, M=6 和数列 4 2 4 5 1，输出 3（划分为 [4,2][4,2]、[4][4]、[5,1][5,1]）。

思路

所有数非负，前缀和单调不减，因此从左到右贪心累加：当前数并入当前段后段和仍不超过 MM 就并入，否则在此切断、另起新段。每一段都尽可能向右延伸，归纳可知任何方案的每段右端点都不会比贪心解更靠右，故段数最少。单次线性扫描即可，时间 O(N)O(N)。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 09:43
# update_at: 2026-09-30 09:43

import sys


def min_segments(seq: list[int], max_sum: int) -> int:
    """计算将序列划分为每段和不超过 max_sum 的最少段数。"""
    count = 1
    current_sum = 0
    for x in seq:
        if current_sum + x <= max_sum:
            current_sum += x
        else:
            count += 1
            current_sum = x
    return count


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return
    m = next(data)
    seq = [next(data) for _ in range(n)]

    ans = min_segments(seq, m)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:30
 * update_at: 2026-10-05 23:30
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 100000 + 5;

int n;              // 数列长度
ll m;               // 每段和的上限
ll a[MAXN];         // a[i]：数列第 i 个数（非负整数）

// 贪心：从左到右扫描，当前段能装就装，装不下就另起一段。
// 因为所有数非负，让每一段尽可能向右延伸一定不劣，段数最少。
int main() {
    scanf("%d %lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }

    int ans = 1;    // 至少分成 1 段
    ll sum = 0;     // 当前段的和

    for (int i = 1; i <= n; ++i) {
        if (sum + a[i] <= m) {
            // 当前数还能放进这一段
            sum += a[i];
        } else {
            // 放不下，另起一段，当前数成为新段第一个数
            ++ans;
            sum = a[i];
        }
    }

    printf("%d\n", ans);
    return 0;
}