二分最大段和，用贪心验证能否在不超过 M 段内完成划分。
OJ: roj
题目 ID: 1243
难度:普及
标签:二分答案贪心前缀和
创建: 2026-09-30 01:19
更新: 2026-10-05 06:30
题目描述
农夫约翰记录下接下来 N 天每天的开销（1 ≤ N ≤ 100,000，每天的开销 ≤ 10,000）。他要把这 N 天恰好分成 M（1 ≤ M ≤ N）个连续的财政周期，使开销最多的那个周期的开销尽可能小。输入第一行为 N、M，接下来 N 行每天的开销；输出最大月度开销的最小值。
样例：N=7, M=5, 开销 = 100, 400, 300, 100, 500, 101, 400，最优划分为 [100,400] | [300,100] | [500] | [101] | [400]，最大月度开销为 500。
思路
二分最大段和 X，贪心地从左到右把每段尽量延长（加到会超 X 就开新段），看最少段数是否 ≤ M；可行性随 X 单调，在 [max(ai), sum(ai)] 上二分即可。
参考代码
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 01:19
# update_at: 2026-09-30 01:19
import sys
from collections.abc import Iterator
def feasible(limit: int, a: list[int], m: int) -> bool:
"""能否把 a 分成不超过 m 段，使每段和都不超过 limit。"""
parts = 1 # 当前段数
total = 0 # 当前累计和
for x in a:
if x > limit: # 单日超限，直接不可行
return False
if total + x <= limit:
total += x
else:
parts += 1
total = x
if parts > m:
return False
return True
def solve() -> None:
data = map(int, sys.stdin.buffer.read().split())
it: Iterator[int] = iter(data)
n = next(it)
m = next(it)
a = [next(it) for _ in range(n)]
lo, hi = max(a), sum(a)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid, a, m):
hi = mid
else:
lo = mid + 1
print(lo)
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 06:30
* update_at: 2026-10-05 06:30
*/
// main.cpp：二分答案 + 贪心验证。
// 思路：在 [max(ai), sum(ai)] 上二分最大段和 X，贪心地从左到右尽量把
// 当前段延长，超出 X 就开启新段；统计最少段数，若 <= M 则 X 可行。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int n, m;
int a[MAXN];
// 判定：在上限 limit 下，能否把序列分成不超过 m 段，使每段和都不超过 limit。
// 贪心：当前段尽量长，超出 limit 就开新段，得到的是最少段数。
bool feasible(int limit) {
int parts = 1; // 当前已分出的段数
int sum = 0; // 当前段累计和
for (int i = 1; i <= n; i++) {
if (a[i] > limit) return false; // 单日就超过上限，必不可行
if (sum + a[i] <= limit) {
sum += a[i]; // 还能放当前段
} else {
parts++; // 开启新段
sum = a[i];
if (parts > m) return false; // 段数超限，已经不可行
}
}
return true;
}
int main() {
scanf("%d %d", &n, &m);
int lo = 0, hi = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
lo = max(lo, a[i]); // 下界：单日最大值（必须能容纳最大的那一天）
hi += a[i]; // 上界：总和（一整段一定可行）
}
// 二分最小的可行上限
while (lo < hi) {
int mid = (lo + hi) / 2;
if (feasible(mid)) {
hi = mid; // mid 可行，尝试更小
} else {
lo = mid + 1; // mid 不可行，必须更大
}
}
printf("%d\n", lo);
return 0;
}