PYTHON LESSON 074
考点精讲：二分答案进阶——最大值最小化
识别“最大值最小化 / 最小值最大化”题型，会写可行性检验函数，掌握二分答案的完整框架。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 答案有单调性才能二分
- check(x)：贪心检验 x 可不可行
- 可行就记下答案并收缩一侧边界
01 · 核心概念
“最大值最小”类问题的二分答案套路
“最大值最小”类问题的二分答案套路：“让最累的人尽量轻松”“让最长一段尽量短”——这类“最大值最小”的问题直接求最优解很难。但反过来，给定一个上限 limit，判断“能不能做到”却很容易：这正是二分答案的舞台。
GESP Python 5 级 · 二分答案复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
答案有单调性才能二分先准确读出这条写法的结构与作用。
check(x)：贪心检验 x 可不可行换一组最小数据，手工推演一次结果。
可行就记下答案并收缩一侧边界再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 二分答案进阶：按顺序把任务分给 k 个人，让最大工作量尽量小
def min_max_load(tasks, k):
"""tasks 按顺序切成 k 段，返回“最大段和”的最小可能值"""
def ok(limit):
cnt = 1
cur = 0
for t in tasks:
if t > limit:
return False
if cur + t > limit:
cnt = cnt + 1
cur = t
else:
cur = cur + t
return cnt <= k
left, right = max(tasks), sum(tasks)
ans = right
while left <= right:
mid = (left + right) // 2
if ok(mid): # 这个上限够用，试试更小的
ans = mid
right = mid - 1
else: # 不够用，只能把上限放大
left = mid + 1
return ans
tasks = [4, 2, 7, 3, 6, 5]
print("任务清单：", tasks, "，总工作量", sum(tasks))
print("分给 2 个人，最大工作量最小为：", min_max_load(tasks, 2))
print("分给 3 个人，最大工作量最小为：", min_max_load(tasks, 3))任务清单： [4, 2, 7, 3, 6, 5] ，总工作量 27 分给 2 个人，最大工作量最小为： 14 分给 3 个人，最大工作量最小为： 11
“最大值最小化”的标准套路：二分上限 + 贪心检验。k = 2 时最优分法是 [4,2,7] 与 [3,6,5]。
04 · 逐步理解
每一步只解决一个问题
- 01
一类新题型：最大值最小化
“让最累的人尽量轻松”“让最长一段尽量短”——这类“最大值最小”的问题直接求最优解很难。但反过来，给定一个上限 limit，判断“能不能做到”却很容易：这正是二分答案的舞台。
- 02
先写检验函数 ok(limit)
按顺序扫描任务：当前这个人装不下，就换下一个人接着装，顺便统计需要几个人。人数不超过 k，说明 limit 够用。任何一个任务单独超过 limit，直接判死刑。
if cur + t > limit: cnt = cnt + 1 cur = t - 03
发现单调性
limit 越大越容易够用，越小越难满足。这种“可行性随答案单调变化”的性质，就是可以二分的通行证。没有单调性，二分答案免谈——动手前先问自己这句话。
- 04
圈定上下界
下界至少是最大那个任务（再小就装不下它），上界取任务总和（一个人全包一定能成）。ans 先记为上界，然后在 [left, right] 上开始二分。
left, right = max(tasks), sum(tasks) - 05
二分的收缩方向
ok(mid) 成立，说明 mid 可行，但也许还能更小：记下答案、砍掉右半；不成立，说明 limit 太小：砍掉左半。收缩方向背反了，答案就南辕北辙。
if ok(mid): ans = mid right = mid - 1 else: left = mid + 1 - 06
和跳石头对照着学
题库里的“跳石头”是反方向的“最小值最大化”：check 可行就把下界往上抬。两个方向只背一个模板，另一个对照着推，考场上就不容易混。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行裁判程序，看 2 人分工的结果
- 2手算验证 14 是最优的最大工作量
- 3把 k 改成 3，观察答案怎么变
- 4给任务清单加一项，先预测再运行验证
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
程序组织类、对象、属性与方法理解对象模型和封装边界，用类表达有状态的实体，而不是把所有程序都强行改成类。＋
正式定义
类描述一类对象的数据与行为；实例是类创建的具体对象。实例方法的第一个参数通常命名为 self，用来访问当前实例；__init__ 在实例创建后负责初始化状态。
必须掌握
- 实例属性通常在 __init__ 中通过 self.name = value 建立。
- 实例方法通过 object.method() 调用；Python 会自动把实例绑定给 self。
- 类属性由实例共享，实例属性属于单个对象；同名实例属性会遮蔽类属性。
- __repr__ 面向开发与调试，__str__ 面向用户显示；特殊方法应遵守其协议。
- 继承表达“是一种”关系，组合表达“拥有一个”关系；能用组合清晰表达时不要滥用继承。
- 对象相等默认仍是身份比较；需要按内容相等时要定义相应协议。
常见误区
- 在方法中漏写 self
- 把每个实例独有的可变数据写成类属性
- 只为包装几个无状态函数而建类
- 继承层次过深导致行为难以追踪
适用边界
- 课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
- 算法题常用函数和基本容器更直接，不要求为了“面向对象”而增加结构。
完成检查