1. 二分答案（binary search on answer）的判定函数设计中如何证明可行性单调，为什么最小化最大值与最大化最小值都能二分？
问题
请说明二分答案（binary search on answer）的判定函数设计，如何证明可行性单调，以及为什么最小化最大值与最大化最小值都能二分？
考察点
- 把最优值问题转化为"给定阈值是否可行"的判定问题
- 可行性关于阈值的单调性（单调递增或递减）
- 最小化最大值（二分上界）与最大化最小值（二分下界）的统一框架
答案
二分答案的核心是：将"求最优值"转化为"对某个答案 x 判断是否存在满足约束的方案"，即设计判定函数 ok(x)。可行性的关键性质是单调性：若 x 可行，则对"最小化最大值"问题，更大的 x 也一定可行（放宽约束）；对"最大化最小值"问题，若 x 可行则更小的 x 也可行。正是这种单调性使候选答案区间可二分。最小化最大值（如把所有数分成若干段使每段和的最大值最小）二分的是"最大值上界"，单调递增可行；最大化最小值（如把牛放到牛棚使最近距离最大）二分的是"最小值下界"，单调递减可行。判定函数需在 O(判定复杂度) 内验证单调性，总复杂度 O(判定*log(值域))。
解析
证明单调性通常是"可行性"的传递性：约束越宽松越容易满足。二分答案的价值是把"优化"变成"判定"，只要判定函数易写，就能用二分把指数/多项式搜索降到 log 倍。关键在于边界写法（何时取 mid、何时收缩）与判定函数严格正确。
示例代码
// 最小化最大值：分 m 段，每段和最大值最小
boolean ok(long x, int[] a, int m) {
long sum = 0; int cnt = 1;
for (int v : a) {
if (sum + v > x) { cnt++; sum = v; } else sum += v;
}
return cnt <= m;
}
long bs(int[] a, int m) {
long lo = 0, hi = (long)2e18;
while (lo < hi) {
long mid = (lo + hi) >>> 1;
if (ok(mid, a, m)) hi = mid; else lo = mid + 1;
}
return lo;
}