数列分段 Section II
二分最大段和，用从左到右尽量装满当前段的贪心检查最少段数。
OJ: luogu
题目 ID: P1182
难度:普及/提高-
标签:二分答案贪心python
日期: 2026-06-22 20:57
题意
给定一个正整数序列，要把它分成 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 读取。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-09 06:46
* update_at: 2026-08-14 19:14
*/
/* P1182 数列分段 Section II */
/* 二分答案：找最小的最大段和，使分段数不超过 m。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
long long a[MAXN]; // 数列
// 最大段和 mid 是否可行：最少分段数不超过 m。
// check 单调：false false ... false true true ... true。
bool check(long long mid) {
int segments = 1;
long long cur_sum = 0;
for (int i = 1; i <= n; i++) {
if (cur_sum + a[i] <= mid) {
cur_sum += a[i];
} else {
segments++;
cur_sum = a[i];
}
}
return segments <= m;
}
// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 check 单调：false false ... false true true ... true。
// 调用时要保证 r 是一个真实或虚拟的可行位置。
long long first_true(long long l, long long r) {
while (l < r) {
long long mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
long long max_a = 0, sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > max_a) max_a = a[i];
sum += a[i];
}
// 总和一定可行（只分 1 段），作为虚拟可行位置
cout << first_true(max_a, sum) << '\n';
return 0;
}Python 教学版本：
Python 代码
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)复杂度
每次检查为
text
O(n log sum)空间复杂度为
总结
本题是典型的“最大值最小”二分答案。
关键是固定答案后用贪心检查最少段数：每段尽量往右扩展，不会让后面更难分，因此这个检查是正确的。