数列分段 Section II

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

二分最大段和，用从左到右尽量装满当前段的贪心检查最少段数。

OJ: luogu

题目 ID: P1182

难度:普及/提高-

标签:二分答案贪心python

日期: 2026-06-22 20:57

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定一个正整数序列，要把它分成 M 段，每段连续。

要求最小化所有段中最大的段和。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const long long INF = (1LL << 60);

int n, m;
long long a[MAXN], prefix_sum[MAXN];
long long dp[MAXN][MAXN];

long long range_sum(int l, int r) {
    return prefix_sum[r] - prefix_sum[l - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            for (int p = 0; p < i; p++) {
                if (dp[p][k - 1] == INF) {
                    continue;
                }
                dp[i][k] = min(dp[i][k], max(dp[p][k - 1], range_sum(p + 1, i)));
            }
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

暴力 DP 可以枚举分段点，但数据范围更适合二分答案。

设答案上限为 limit。我们只需要判断：能否把序列分成不超过 M 段，并且每段和都不超过 limit。

检查方法很简单：从左到右扫描，当前段能放就继续放；如果再放会超过 limit，就新开一段。

这样得到的是在 limit 限制下的最少段数。如果最少段数不超过 M，说明 limit 可行；否则不可行。

可行性随 limit 增大而单调变好，所以可以二分最小可行值。

Python 知识

  • left = max(numbers)、right = sum(numbers) 直接给出答案的紧二分边界。
  • 判定函数按值遍历列表，用 current_sum 和 segments 表达当前段与已用段数。
  • 正整数保证“当前段尽量装满”能得到固定上限下的最少段数。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：聚合函数与可迭代对象的使用边界。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量整数 token 读取。

代码

python
import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n, segment_limit = data[:2]
numbers = data[2:2 + n]


def possible(maximum_sum):
    segments = 1
    current_sum = 0
    for number in numbers:
        if current_sum + number <= maximum_sum:
            current_sum += number
        else:
            segments += 1
            current_sum = number
    return segments <= segment_limit


left, right = max(numbers), sum(numbers)
while left < right:
    middle = (left + right) // 2
    if possible(middle):
        right = middle
    else:
        left = middle + 1

print(left)

复杂度

每次检查为 O(n)O(n)，二分答案范围，总时间复杂度为：

text
O(n log sum)

空间复杂度为 O(n)O(n)。

总结

本题是典型的“最大值最小”二分答案。

关键是固定答案后用贪心检查最少段数：每段尽量往右扩展，不会让后面更难分，因此这个检查是正确的。