「一本通 1.2 练习 1」数列分段 II

形式化题目

给定长度为 $n$ 的非负整数数列 $a_1, \dots, a_n$ 与整数 $m$ （ $m \leqslant n$ ），把数列划分成 $m$ 个连续的段，最小化所有段和中的最大值。

正解

思路

直接枚举分段方案是指数级的。换一个方向：先猜答案，再验证。

设答案为 $x$ ，即"每段和都不超过 $x$ "。给定 $x$ ，最少需要几段可以用贪心求出：从左到右依次累加，当前元素放得进本段就放，放不下就另起一段。这样每一段都尽量装满，得到的段数 $f(x)$ 就是以 $x$ 为上限时的最少段数；只要 $f(x) \leqslant m$ ，就存在一种合法的分法。

关键观察是单调性： $x$ 越大，每段能装下的元素越多， $f(x)$ 只会变少或不变。所以 $f(x) \leqslant m$ 在 $x$ 上具有单调性，可以对 $x$ 二分：

下界取 $\max a_i$ ：任何一段至少要装下一个元素；
上界取 $\sum a_i$ ：整个数列一段分完。

二分中点 $mid$ ，若 $f(mid) \leqslant m$ 则答案 $\leqslant mid$ ，收缩右端；否则收缩左端。

用样例「4 2 4 5 1， $m=3$ 」演示判定过程，下表展示不同上限 $x$ 对应的贪心分段与最少段数：

上限 $x$	贪心分段	最少段数 $f(x)$	$f(x) \leqslant 3$ ？
5	[4] [2] [4] [5] [1]	5	否
6	[4 2] [4] [5 1]	3	是
9	[4 2] [4 5] [1]	3	是
15	[4 2 4 5] [1]	2	是

可以看到 $f(x)$ 随 $x$ 增大单调不增，从"否"翻转为"是"的临界点就是答案 $6$ ，与样例输出一致。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def count_segments(a: list[int], limit: int) -> int:
    """上限为 limit 时最少分几段：贪心累加，放不下就另起一段。"""
    segments, cur = 1, 0
    for x in a:
        cur_add = cur + x
        if cur_add <= limit:
            cur = cur_add                        # 还塞得进当前段
        else:
            segments += 1                        # 另起一段
            cur = x
    return segments


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

    # 答案 x 的判定具有单调性：x 越大，最少段数越少，在 [max(a), sum(a)] 上二分
    lo, hi = max(a), sum(a)                      # 每段至少装下最大元素；最多一段装下全部
    while lo < hi:
        mid = (lo + hi) // 2
        can = count_segments(a, mid) <= m        # 上限 mid 时段数不超限 → 答案 ≤ mid
        if can:
            hi = mid
        else:
            lo = mid + 1

    print(lo)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * 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 01:00
 * update_at: 2026-10-05 01:00
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;       // 数列长度
ll m;        // 要求分成的段数
ll a[MAXN];  // 题目给出的数列，下标从 1 开始

// 判断上限 x 是否可行：贪心从左往右累加，放不下就另起一段，
// 返回以 x 为每段和上限时的最少段数是否不超过 m。
// 贪心正确性：每一段尽量装满，交换论证可证段数不会更多。
bool check(ll x) {
    ll cnt = 1;   // 当前已经用掉的段数，至少有一段
    ll sum = 0;   // 当前段的和
    for (int i = 1; i <= n; ++i) {
        if (sum + a[i] <= x) {
            sum += a[i];      // 还塞得进当前段
        } else {
            cnt++;            // 另起一段
            sum = a[i];
        }
    }
    return cnt <= m;
}

void solve() {
    scanf("%d %lld", &n, &m);
    ll maxa = 0, sumall = 0;   // 二分下界：至少装下最大元素；上界：一段装下全部
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        maxa = max(maxa, a[i]);
        sumall += a[i];
    }

    // 答案 x 具有单调性：x 越大，最少段数越少，在 [maxa, sumall] 上二分
    ll lo = maxa, hi = sumall;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;          // 可行：答案可能是 mid 或更小
        } else {
            lo = mid + 1;      // 不可行：mid 太小
        }
    }

    printf("%lld\n", lo);
}

int main() {
    solve();
    return 0;
}

复杂度

时间：每次判定 $O(n)$ ，二分 $O(\log \sum a_i)$ 轮，总计 $O(n \log \sum a_i)$ 。本题 $n \leqslant 10^5$ 、 $a_i \leqslant 10^5$ 量级，非常宽裕。
空间： $O(n)$ 存数列。

总结

本题是"最大化最小值 / 最小化最大值"类问题的经典范式：**答案本身具有单调性时，二分答案

贪心判定**。贪心判定的正确性来自交换论证——把任何合法方案的第一段右端点右移到贪心位置仍然合法，逐段调整后段数不会增加。二分结束的条件是左右端点重合，此时 $lo$ 就是最小的可行上限。

图示解析

flowchart TD
    A["答案 x"] -->|"判定 f(x) ≤ m ?"| B{"贪心分段"}
    B -->|"是：x 可能更小"| C["右端收缩 hi = mid"]
    B -->|"否：x 太小"| D["左端收缩 lo = mid + 1"]
    C --> E{"lo < hi ?"}
    D --> E
    E -->|"是"| B
    E -->|"否：lo 即答案"| F["输出 lo"]

上图展示二分答案的整体流程：每轮用 $O(n)$ 贪心求出上限 $mid$ 下的最少段数，按可行与否收缩二分区间。观察重点是"判定可行 → 答案在左半"、"判定不可行 → 答案在右半"这一单调收缩过程，它保证最终左右端点重合处就是最小的可行上限。