最大化最小值 / 最小化最大值 - 算法套路总结
一、什么是"最大化最小值"问题？
在算法题中，经常会遇到这样的描述：
- “让所有工人的最大工作量尽可能小”
- “让所有城市的最小电量尽可能大”
- “让木材切割后的最小长度尽可能大”
- “让学生分配到的最大任务数尽可能小”
这类问题有个共同特点：求在某种约束条件下，某个极值指标的最优值。
乍一看这类问题很难直接求解，但有一个巧妙的思路：把"求最优值"转换为"判断某个值是否可行"。
二、核心思想：二分答案法
2.1 为什么要二分答案？
直接思路的困境：
假设要求"分配任务后，学生们的最大任务量的最小值"，如果直接枚举所有可能的分配方案，复杂度会是指数级的，根本无法接受。
转换思路：
我们换个角度问问题：
- 原问题：“最优答案是多少？”（不知道怎么求）
- 新问题：“答案能否达到 X？”（相对容易判断）
如果能高效判断"答案是否能达到 X"，那我们就可以用二分搜索在所有可能的答案中找到最优的那个！
2.2 为什么二分法有效？关键在于单调性
二分答案法之所以可行，是因为这类问题有一个关键性质：单调性。
以"最大化最小值"为例：
- 如果"让所有城市电量都达到 10"可以实现，那么"让所有城市电量都达到 9、8、7…"肯定也可以实现（要求更低了）
- 如果"让所有城市电量都达到 10"无法实现，那么"让所有城市电量都达到 11、12、13…"肯定也无法实现（要求更高了）
这种单调性意味着：存在一个临界值 M，小于等于 M 的都可以实现，大于 M 的都无法实现。
答案值: 0 1 2 3 4 5 6 7 8 9 10 11 12
是否可行: ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✗ ✗ ✗ ✗
↑
我们要找的最优答案
这正是二分搜索的应用场景！我们要找的就是那个"从可行到不可行"的临界点。
三、解题框架（四步走）
第一步：识别问题类型
看到以下关键词就要想到二分答案法：
- “最大化最小值”
- “最小化最大值”
- “在…约束下，求…的最优值”
- “让…尽可能大/小”
第二步：确定二分搜索范围
需要确定答案的可能范围 [left, right]：
- left（最小可能值）：通常是理论最小值，比如 0，或者初始状态下已有的最小值
- right（最大可能值）：通常是理论最大值，比如所有资源之和，或者题目给定的上限
第三步：设计 check(mid) 函数
这是最关键的一步！
check(mid) 函数的作用：判断答案能否达到 mid。
- 返回
true：说明 mid 这个答案可以实现，真正的最优答案 ≥ mid - 返回
false：说明 mid 这个答案无法实现，真正的最优答案 < mid
设计 check 函数时，通常会用到贪心、滑动窗口、差分数组等技巧。
第四步：二分搜索主循环
def solve():
left, right = 确定搜索范围
while left < right:
mid = (left + right + 1) // 2 # 对于"最大化最小值"问题
if check(mid): # mid 可行
left = mid # 尝试更大的值
else: # mid 不可行
right = mid - 1 # 尝试更小的值
return left # 最终 left == right，就是答案
注意：
- "最大化最小值"问题：
mid = (left + right + 1) // 2，可行时left = mid - "最小化最大值"问题：
mid = (left + right) // 2，可行时right = mid
