按序分苹果
P6086. 按序分苹果
场次:2026年10月23日-非AI方向 · 来源:CodeFun2000 P6086
题目描述
园长阿姨手里捧着 个苹果,分量各不相同,从左到右的重量记作 。班里有 个小朋友,按学号从前往后站成一行。这些苹果要顺着站位发下去,规则有两条:
不许剩下:每个人至少领一个,苹果也要全部发出去。
尽量匀一些:每个人领到的分量之和要彼此靠近。
请给出一个最小的数。它是所有发法里,各人拿到的总重量中最大的那一份,再把这个最大份压到最低。
换句话说,每种发法先记下最沉的那一份,再在这些记录当中取最小的一个。
苹果必须维持现在的左右次序,只能从左往右切成 段连续苹果。第 段交给站在最前的小朋友,后面各段按站位依次往后交。不相邻的苹果不能抽出来交给同一个人。
举个小例子。三个苹果重量是 ,发给 个小朋友。切成 与 ,两份是 和 ,最沉的是 ;切成 与 ,两份是 和 ,最沉的是 。所以最低能压到 。
输入格式
第一行给出两个整数 和 。 是苹果有多少个, 是小朋友有多少人。
第二行给出 个整数 ,按从左到右的次序写每个苹果的重量。
数据范围:
输出格式
只写出一个整数,表示最沉那一份能够压到的最小重量。
示例
示例 1
输入:
4 3
4 1 5 2输出:
5说明: 要切成 段,只能在相邻苹果之间下刀。
,三份是 、、,最沉 。
,三份是 、、,最沉 。
,三份是 、、,最沉 。
最低能压到 ,对应最后一种切法。
示例 2
输入:
5 2
3 6 1 4 2输出:
9说明: 切成 段时,下刀的位置只有四种:
与后面, 和 ,最沉 。
与后面, 和 ,最沉 。
与后面, 和 ,最沉 。
与后面, 和 ,最沉 。
四种里最沉份的最小值是 。
解题思路
输出到底是什么:所有切法里「最沉那一份」的最小值
题目要的不是某一种切法,而是一个数:
「合法切法」= 把数组从左到右切成 段连续、非空的区间,中间不能跳着挑,也不能有空段。这一步读清楚很关键:它把问题限定成「在 个空隙里挑 个下刀」,而不是「任意把苹果分组」。
数据范围的两个信号:枚举切法不通,但答案的取值范围很小
最直白的做法是枚举所有切法。下刀位置是从 个空隙里挑 个,所以最坏是
条分支,连存都存不下,这条路直接断掉。
再看另一头:,,所以总和不超过 。答案(最沉那一份的最小值)必然落在
这个区间里,最多只有 个整数候选。候选少、判定容易,这正是「二分答案」的两个前提:不枚举方案,而是枚举答案,把「求最小值」换成「给定一个上限,问能不能做到」。
单调性:把「能不能」问出来,答案就能二分
对给定的上限 ,记一个问题:能否切成不超过 段,使每段的和都 ?
- 若 能做到,那么 一定也能做到 —— 同一套切法在更宽松的上限下依然合法;
- 若 做不到,那么 也做不到 —— 限制更紧,能用的切法只会更少。
这就是二分的单调性。于是「最小的可行 」可以把区间一分为二:mid 可行就说明答案不超过 mid,否则答案至少是 mid + 1。
给定上限后,怎么判定:从左往右能塞就塞
判定不需要搜索,一遍扫描就够:维护当前这一段已经装了多少,遇到下一个苹果时,装得下就装,装不下就把它作为新一段的开头。
def feasible(limit):
groups, cur = 1, 0 # 第一段已经开始
for w in g:
if cur + w > limit: # 装不下 -> 另起一段
groups += 1
cur = w
if groups > b: # 段数已经超过小朋友人数,不用再看
return False
else:
cur += w
return True为什么这样数出来的段数是最少的。 设贪心的第 段右端点在 ,任意一种合法切法的第 段右端点在 。第一段:贪心一直装到装不下为止,右端点不可能更靠右,所以 。若 ,则第 段的起点不早于贪心的第 段,可用的苹果更少,右端点也不会超过 。归纳下来 对每一层都成立。
于是「存在一种 段的切法」等价于「贪心数出来的段数 」:贪心段数最少,它都超过 了,别人只会更多;它没超过 ,它自己就是一种可行切法。
「恰好 段」与「至多 段」是同一件事
题面要求每人至少一个、苹果全部发完,也就是恰好切成 段。而判定里写的是 groups <= b,两者能划等号,靠的是 :
- 贪心给出 段,,每段至少一个苹果;
- 若 ,因为总苹果数 ,必有某一段的长度 (否则 ,矛盾);
- 把这一段从中间切开,段数 ,两份都非空,而且两份的和都不超过原来那一段的和,仍然 。
反复切到 段即可,所以「能切成至多 段」与「能切成恰好 段」在本题的约束下完全等价。若题面没有 这个保证,这一步就不成立了。
二分与边界的写法
lo, hi = max(g), sum(g) # 下界:最重的那颗苹果无法劈开;上界:全部给一个人
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid 可行,答案不超过 mid
else:
lo = mid + 1 # mid 不可行,答案至少是 mid + 1
print(lo)下界取 max(g) 而不是 ,是因为一颗苹果不能被分给两个人:只含这颗苹果的那一段,和至少是它自己的重量。上界取总和,对应「前 段各留一个苹果、剩下全给最后一个人」这种一定合法的切法( 保证前 段都有苹果可留)。
实现落点
groups, cur = 1, 0:第一段在循环开始前就存在,所以段数从 起,不能从 起;cur + w > limit而不是>=:装到正好等于上限是合法的,写成>=会提前切断,数出来的段数偏多;if groups > b: return False:段数一旦超过人数就可以停,剩下的苹果只可能让段数继续增加;- 循环结束
lo == hi,直接输出lo,不需要再调用一次判定。
完整代码实现
"""
P6086. 按序分苹果 - 二分答案 + 贪心判定
把 A 个苹果按原顺序切成 B 段连续非空区间,使「各段和的最大值」尽量小,
输出这个最小值。
输入格式:
- 首行两个整数 A、B,分别是苹果数与小朋友人数;
- 次行 A 个整数,按从左到右的次序给出每个苹果的重量。
输出格式:
- 一个整数:最沉那一份能压到的最小重量。
核心思路:
答案是「最沉那份」的最小值,候选只有 [max(g), sum(g)] 这么多个,且
「上限 L 是否可行」具有单调性,于是二分 L。判定用一遍贪心:从左往右
能装就装,装不下就另起一段,数出的段数是最少的;段数 ≤ B 即可行
(B ≤ A,段数不足时可以继续把某一段切开)。
时间复杂度:O(A * log(sum(g)))
空间复杂度:O(A)
"""
# https://codefun2000.com/p/P6086
import sys
# @sample-start
"""
样例输入 1:
4 3
4 1 5 2
样例输出 1:
5
"""
# @sample-end
# @sample-start
"""
样例输入 2:
5 2
3 6 1 4 2
样例输出 2:
9
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
a = int(data[0])
b = int(data[1])
g = [int(x) for x in data[2:2 + a]]
def feasible(limit):
groups, cur = 1, 0 # 第一段已经开始
for w in g:
if cur + w > limit: # 装不下 -> 另起一段
groups += 1
cur = w
if groups > b: # 段数已超人数,后面只会更多
return False
else:
cur += w # 装得下就继续装
return True
lo, hi = max(g), sum(g) # 下界:最重的一颗;上界:全给一个人
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid 可行,答案不超过 mid
else:
lo = mid + 1 # mid 不可行,答案至少 mid + 1
print(lo)
def run_tests():
"""运行嵌入的示例,方便本地自测。"""
import io
cases = [
("4 3\n4 1 5 2\n", "5"),
("5 2\n3 6 1 4 2\n", "9"),
# 两人各一颗,谁也不能少 -> 最重的那颗
("2 2\n5 1\n", "5"),
# 每个人只领一颗:答案就是最重的那颗
("4 4\n5 1 1 1\n", "5"),
# 一个人领全部
("3 1\n2 5 1\n", "8"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:,,重量
答案的搜索区间是 。
第 1 轮: lo=5, hi=12,mid = 8。用上限 扫一遍:
| 苹果 | 当前段和(装之前) | 装进后 | 段数 |
|---|---|---|---|
| ,另起一段 | (新段为 ) | ||
段数 ,可行 → hi = 8。
第 2 轮: lo=5, hi=8,mid = 6。上限 :
- 装进第 1 段(和 ); 跟进去(和 );下一颗 装不下(),另起第 2 段,和为 ;
- 最后 装进第 2 段变 ,再另起第 3 段,和为 。
段数 ,可行 → hi = 6。
第 3 轮: lo=5, hi=6,mid = 5。上限 :
- 与 恰好装满第 1 段();
- 单独成第 2 段;
- 单独成第 3 段。
段数 ,可行 → hi = 5。
此时 lo = hi = 5,输出 。
这个结果与题面列举的三种切法一致:切法 的三份正是 ,最沉的一份是 ;而 又是单颗苹果 逼出来的下界,两边顶住,所以它一定是最小值。
为什么 不可能是答案
确实可行(切法 里最沉的是 ),但题面问的是最小值:只要 也可行, 就不是答案。二分的 hi = mid 正是这个意思 —— 可行只说明「答案不超过 mid」,不说明 mid 就是答案。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有切法 | 时组合数达到 量级,必然超时 | ||
| 二分答案 + 贪心判定(最优) | 候选区间不超过 ,二分约 轮,每轮扫一遍数组 |
时间里的 来自二分:区间长度最多 ,所以最多 轮;每轮判定是 的一遍扫描,而且一旦段数超过 就提前退出。空间上除了读入的数组,判定只需要两个计数器。
易错点总结
1. cur + w > limit 写成 >=
判定里把「装不下才另起一段」写成「装满也另起一段」(if cur + w >= limit),会把正好等于上限的苹果切断。示例 1 在上限 时, 会被误判成装不下,于是段数变成 ,feasible(5) 返回 False,二分把答案推到 ,示例 1 输出 (正确 )。
2. 下界写成 0 或 1
lo 不从 max(g) 起步时,二分会在「某颗苹果本身就超过上限」的区间里做判定,而判定只数字段数、不检查单颗苹果是否超限。例如输入 4 4 配 5 1 1 1:上限 时贪心把第一段硬塞成 (这一段的真实和已经超过上限),后面三个 合成一段,数出来的段数是 ,被判成可行;二分于是继续下探,最终输出 (正确 )。样例 1 恰好不会暴露这一点,因为它的下界 正好就是答案。
3. 判定写成「段数恰好等于 」
把 if groups <= b 写成 if groups == b(或 groups != b 时判不可行),就丢掉了「段数不足时可以继续切开」这一步。示例 1 在上限 时段数是 ,被误判成不可行,二分一路往上推,最终输出 (正确 )。