答案空间二分

数学 / 逻辑形态

对最小化问题构造 F…F T…T 的 can(x)，寻找 first True；对最大化问题构造 T…T F…F，寻找 last True。

识别信号

题目要最小化最大值或最大化最小值。
给定阈值后，验证是否可行明显比直接求最优容易。
候选答案属于可界定的整数/离散值域。
提高资源、时间或容量不会使原本可行的方案失效。

容易误判的相似信号

Signal	Why it is different
可行性不单调	x 增大后方案可能先可行再不可行，二分不能用。
值域巨大且谓词昂贵	理论可用不代表实际最佳；可能有直接贪心、堆或选择算法。

核心不变量

闭区间 [lo,hi] 始终包含目标边界；对于 first True，hi 是已知或潜在可行候选，lo 左侧已排除。

状态、转移与处理顺序

Item	Definition
State	答案下界 lo、可行上界 hi、mid，以及只回答可行/不可行的 can(mid)。
Transition	can(mid) 真则保留 mid：hi=mid；否则 lo=mid+1。
Frontier / order	尚未判定的答案值域；每轮通过完整可行性检查砍掉一半。

Python 骨架

def minimize_feasible(lo, hi, can):
    # Precondition: the optimum is in [lo, hi] and can(hi) is True.
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

正确性思路

若 mid 可行，最小可行值至多为 mid，因此保留左半含 mid。
若 mid 不可行，单调性保证所有更小值也不可行，可整体排除。
区间收敛到一个仍满足不变量的值，它既可行又没有更小可行值。

复杂度

Time	Space	Parameters
O(C log W)	O(S)	W=hi-lo+1 为答案域宽度；C、S 分别为一次 can 的时间和空间。

边界条件

lo/hi 必须来自语义而非随意常数。
can(hi) 若不保证为真，应先扩上界或验证无解。
目标值可能只取输入中的离散候选，可二分排序去重后的候选表。
整数溢出语言中用 lo+(hi-lo)//2。

错误模式

Pattern	Why it fails / fix
在 can 中求了完整最优	谓词只需回答阈值是否足够，保持简单且可单调证明。
二分方向反了	先写出 False/True 图，再决定可行时收左还是收右。
复杂度漏乘 log W	每次谓词成本 C 会执行对数次。

选择与排除规则

先问“若我猜答案为 x，能否 O(C) 验证？”
再证明 x 增大时可行性只朝一个方向变化。
比较 C log W 与直接算法；二分不是自动更快。

Relation	Template	Boundary
阈值路径替代	Minimax / Bottleneck Dijkstra	最小瓶颈既可有序扩张也可二分阈值。
多查询替代	离线排序 + 逐步激活 + 并查集	大量 can(t) 会重复搜索
长度搜索组合	Rolling Hash / Rabin–Karp	存在长度 L 的重复结构具有单调性

原创微型例子

环节	内容
Result	首个可行容量 7 即最小答案。
Setup	要在 D 天内处理工作量，猜测每日容量 x，并贪心判断能否完成。
Trace	容量小于 7 全失败，7 及以上全成功；二分只调用 can(x)。

Recall prompts

minimize maximum 为什么常产生 first True？
总复杂度为何必须乘谓词成本？
如何系统地找 lo 和 hi？

数学 / 逻辑形态

识别信号

容易误判的相似信号

核心不变量

状态、转移与处理顺序

Python 骨架

正确性思路

复杂度

边界条件

错误模式

选择与排除规则

相关模板

原创微型例子

Recall prompts

我的补充