第 44 章 二分¶
配套例题：BISHI85 【模板】整数域二分、BISHI86 圆覆盖、BISHI87 [CQOI2010] 扑克牌、 BISHI88 小苯的魔法染色、BISHI89 山峰数组计数、BISHI91 拼接木棍 来源：S3 day4《二分法及题目选讲》（fstqwq）；《序列算法选讲》（阮行止）第 28–30 页； S4
模板.docx二分 / 二分答案 / 三分
二分是用 \(O(\log n)\) 次判定，在一个有序（或单调）的空间里定位答案。 课件把它分成两类，这个分法非常好用：
| 类型 | 空间 | 判定 | 典型 |
|---|---|---|---|
| 二分查找 | 有序数组的下标 | a[mid] 与目标比较 |
找第一个 \(\ge x\) 的位置 |
| 二分答案 | 答案的值域 | check(mid) 是否可行 |
「最大值最小」「最小值最大」 |
两者的代码骨架完全一样，区别只在「拿什么当判定」。
Python 选手的第一原则：能用 bisect 就绝不手写。手写二分的边界错误是竞赛里
最难查的 bug 之一，而 bisect 是 C 实现且经过千锤百炼。
44.1 bisect：优先选项¶
from bisect import bisect_left, bisect_right, insort
bisect_left(a, x) # 第一个 >= x 的下标（等于 x 的元素若存在，落在返回值右边）
bisect_right(a, x) # 第一个 > x 的下标（等于 x 的元素若存在，落在返回值左边）
insort(a, x) # 保持有序地插入：定位 O(log n)，但列表搬移是 O(n)
所有常见需求都能由这两个函数拼出来，这张表建议直接背：
需求（a 已升序） |
写法 |
|---|---|
| 第一个 \(\ge x\) 的下标 | bisect_left(a, x) |
| 第一个 \(> x\) 的下标 | bisect_right(a, x) |
| 最后一个 \(< x\) 的下标 | bisect_left(a, x) - 1 |
| 最后一个 \(\le x\) 的下标 | bisect_right(a, x) - 1 |
| \(x\) 出现的次数 | bisect_right(a, x) - bisect_left(a, x) |
| 值在 \([l, r]\) 内的元素个数 | bisect_right(a, r) - bisect_left(a, l) |
| \(x\) 是否存在 | i = bisect_left(a, x); i < len(a) and a[i] == x |
三个额外能力：
bisect_left(a, x, lo, hi) # 限定搜索区间 [lo, hi)：左闭右开，比切片省一次 O(n) 复制
bisect_left(keys, x) # 3.10+ 支持 key= 参数；3.9 需自建 keys 数组
Python 3.9 的
bisect没有key参数（3.10 才加）。 要按某个字段二分时，3.9 的做法是先抽出一个纯关键字数组：本教程按 3.9 编写，一律用这种写法。
降序数组怎么办¶
bisect 只认升序。降序数组有两种处理：
# 方案一（推荐）：存相反数，转成升序
a_neg = [-v for v in a] # 取负把降序翻成升序，大小关系整体反转
i = bisect_left(a_neg, -x) # 查找目标也要取负，才对应原来的那个位置
# 方案二：手写二分（见 44.2）
44.2 整数二分的四种边界写法¶
必须手写时（比如二分答案），把下面四个模板抄进代码即可。
它们的区别只在「循环条件」「mid 取法」「谁 = mid」三处，一定要成套记忆。
写法一：找第一个满足 check 的位置（下界）¶
def lower(lo, hi, check):
"""在 [lo, hi] 上找最小的 x 使 check(x) 为真。
要求 check 单调：False...False True...True。若全 False 返回 hi+1。"""
hi += 1 # 哨兵：搜索范围扩成 [lo, hi+1]，多出的那一格代表「不存在」
# 循环不变量：答案一定落在闭区间 [lo, hi] 里
# （lo 左边的都已确认为 False，hi 右边的即使为 True 也不是最小的）
while lo < hi: # lo == hi 时区间只剩一个数，它必然就是答案
mid = (lo + hi) // 2 # 向下取整。由 lo < hi 可得 lo <= mid < hi
if check(mid):
hi = mid # mid 满足条件，它自己可能就是最小的，必须留在区间里
else:
lo = mid + 1 # mid 不满足，比它小的更不满足，答案只可能在右半边
# 不死循环的理由：hi = mid 时因 mid < hi 而右端严格左移，lo = mid+1 时左端严格右移，
# 两支都让区间长度至少减 1，所以最多 log2(hi-lo+1) 轮就收敛
return lo
写法二：找最后一个满足 check 的位置（上界）¶
def upper(lo, hi, check):
"""在 [lo, hi] 上找最大的 x 使 check(x) 为真。
要求 check 单调：True...True False...False。若全 False 返回 lo-1。"""
lo -= 1 # 哨兵：搜索范围扩成 [lo-1, hi]，多出的那一格代表「不存在」
# 循环不变量：答案一定落在闭区间 [lo, hi] 里
while lo < hi: # lo == hi 时区间只剩一个数，它必然就是答案
mid = (lo + hi + 1) // 2 # 注意 +1，向上取整！由 lo < hi 可得 lo < mid <= hi
if check(mid):
lo = mid # mid 满足条件，它自己可能就是最大的，必须留在区间里
else:
hi = mid - 1 # mid 不满足，比它大的更不满足，答案只可能在左半边
# 上取整是这里唯一的保命符：它保证 mid > lo，于是 lo = mid 也让左端严格右移。
# 若用下取整，hi == lo+1 且 check(lo) 为真时 mid == lo，区间纹丝不动，直接死循环
return lo
+1是写法二的生命线。若写成(lo + hi) // 2，当hi = lo + 1且check(lo)为真时，mid = lo，于是lo = mid = lo——区间不缩小，死循环。口诀：谁取
mid谁就要防死循环。lo = mid就要mid上取整。
写法三：闭区间 + 显式返回（最接近 C++ 教材）¶
def binary_search(a, target):
"""在升序数组里找 target，返回下标；不存在返回 -1。"""
lo, hi = 0, len(a) - 1 # 搜索范围是闭区间 [lo, hi]，两端都还没被检查过
# 循环不变量：target 若存在，一定落在 a[lo..hi] 里
while lo <= hi: # 注意是 <=：lo == hi 时区间还剩一个元素，仍要查
mid = (lo + hi) // 2
if a[mid] == target:
return mid # 命中即返回，不必等区间收敛
if a[mid] < target:
lo = mid + 1 # a[mid] 偏小，mid 及其左边全部排除
else:
hi = mid - 1 # a[mid] 偏大，mid 及其右边全部排除
# 两支都把 mid 本身踢出区间，所以区间每轮至少缩短 1，不会死循环
return -1 # 循环因 lo > hi（区间为空）退出，说明不存在
写法四：l/r 各退一步（不需要哨兵，靠不变量）¶
def split_point(lo, hi, check):
"""维持不变量：check(lo) 恒真、check(hi) 恒假。返回最后一个真的位置。
调用前必须保证 check(lo) 为真、check(hi) 为假。"""
while hi - lo > 1: # 收敛到 lo 与 hi 相邻为止，分界线就夹在两者之间
mid = (lo + hi) // 2 # 由 hi - lo >= 2 可得 lo < mid < hi，赋给谁都能缩短区间
if check(mid):
lo = mid # mid 为真 -> 把「真」的右边界推到 mid
else:
hi = mid # mid 为假 -> 把「假」的左边界拉到 mid
# 因为 mid 严格落在两端之间，两支都让区间至少缩短 1，不存在下取整式的死循环
return lo # 不变量保证：lo 是最后一个真，hi 是第一个假
四种写法的对照：
| 写法 | 循环条件 | mid |
收敛后 | 适用 |
|---|---|---|---|---|
| 一（下界） | lo < hi |
下取整 | lo == hi |
最小的可行解 |
| 二（上界） | lo < hi |
上取整 | lo == hi |
最大的可行解 |
| 三（闭区间） | lo <= hi |
下取整 | lo > hi |
精确查找 |
| 四（不变量） | hi - lo > 1 |
下取整 | 相邻 | 分界点，两边都要 |
建议只记住写法一和写法二，其余用
bisect。 两者的记忆锚点： 求最小 →hi = mid，mid下取整；求最大 →lo = mid，mid上取整。
Python 里不用担心的两件事¶
mid = (lo + hi) // 2 # ✅ Python 整数无上限，lo + hi 再大也不会溢出
mid = lo + (hi - lo) // 2 # C++ 里的防溢出写法；两式在 lo <= hi 时结果相同，Python 不需要
但必须用 // 而不是 /——/ 返回 float，当下标会直接 TypeError，
当值域二分时会悄悄丢精度。见
03-运算符与位运算。
44.3 二分答案¶
课件对这类题的总结非常精准：
通常来说，二分答案题目为下列两种中的一种： ① 给定评价函数，求其最小 / 最大值；② 给定条件，在满足条件的同时使代价最小。 计算函数或判断条件很慢，或者值域太大不能一一枚举。
题面里的信号词：
| 出现这些字眼 | 往二分答案想 |
|---|---|
| 「最大值最小」/「最小值最大」 | ⭐⭐⭐ 几乎必是 |
| 「最少需要多少 ×× 才能……」 | ⭐⭐ |
| 「使得所有 ×× 都不超过 \(k\)，求最小的 \(k\)」 | ⭐⭐⭐ |
| 「第 \(k\) 小的数是多少」 | ⭐⭐（二分值 + 数有多少个 \(\le\) 它） |
标准骨架：
def solve():
def check(x):
"""答案取 x 时是否可行。必须对 x 单调：一旦某个 x 可行，更大的 x 也必须可行。"""
...
return True
lo, hi = 0, UPPER # 上界要给足，保证 check(hi) 为真，否则返回值没有意义
# 与 44.2 写法一同构：求最小可行解 -> mid 下取整、可行时 hi = mid
while lo < hi:
mid = (lo + hi) // 2
if check(mid):
hi = mid # mid 可行，它自己可能就是最小的，保留
else:
lo = mid + 1 # mid 不可行，答案只可能更大
return lo # 收敛到 lo == hi，即最小的可行答案
两步走（课件原话）：① 观察单调性，找到需要计算的条件；② 二分并验证条件。 难点永远在 ①②，而不在二分本身。
check 常用的实现手段 |
例子 |
|---|---|
| 贪心 | 跳石头、魔法染色（BISHI88） |
| 前缀和 / 差分 | NOIp 2012 借教室 |
| DP | 划分成 \(k\) 段使最大段和最小 |
| 数据结构 | NOIp 2015 运输计划（树上差分） |
| 直接求和 | 扑克牌（BISHI87） |
课件的另一句提醒：「不是要死磕在二分法上。如果验证方法足够优秀， 完全可以抛弃二分，直接使用优秀的方法求得答案。」 比如 BISHI89 可以二分，也可以直接双指针；BISHI118 更是排序后一遍扫完。 二分是保底手段，不是唯一手段。
44.4 实数二分：固定迭代次数，不要用 while r - l > eps¶
课件里的 C++ 写法是 while (right - left > precision)。
在竞赛里更推荐固定迭代次数：
lo, hi = 0.0, 1e18 # 答案始终夹在 lo 与 hi 之间
for _ in range(100): # 固定 100 次，绝不死循环
mid = (lo + hi) / 2 # 实数域用 / 而不是 //，这里不需要取整
if check(mid):
hi = mid # mid 可行 -> 答案不超过 mid（求最小可行值）
else:
lo = mid # 实数没有「下一个数」，所以是 lo = mid 而非 mid + 1
print("%.6f" % lo) # 收敛后 lo 与 hi 之差远小于精度要求，输出哪个都行
| 写法 | 风险 |
|---|---|
while hi - lo > 1e-9 |
当 lo、hi 很大时（如 \(10^{18}\)），浮点精度不足以让差值降到 \(10^{-9}\)，死循环 |
for _ in range(100) |
每次区间减半，100 次后区间长度是初始的 \(2^{-100} \approx 10^{-30}\)，远超任何精度要求 |
迭代次数怎么选：区间初长 \(L\)，要求精度 \(\epsilon\)，则需要 \(\log_2(L/\epsilon)\) 次。
\(L = 10^{18}\)、\(\epsilon = 10^{-9}\) 时约 90 次，取 100 稳妥。
double 只有 53 位尾数，超过 100 次迭代纯属浪费（区间已经小到浮点无法表示）。
实数二分的另一条铁律：能转成整数二分就转。 比如「求最小半径 \(r\)」的题，二分 \(r^2\)（整数）比二分 \(r\)（实数）更精确， 最后再开方输出。BISHI86 就是这种情况。
44.5 三分：单峰函数求极值¶
二分要求单调，三分只要求单峰（先增后减，或先减后增）。
def ternary_max(lo, hi, f):
"""求单峰函数 f 在 [lo, hi] 上的最大值点（实数域）。"""
for _ in range(200): # 每次区间缩到 2/3，200 次足够
m1 = lo + (hi - lo) / 3 # 两个三等分点，恒有 m1 < m2
m2 = hi - (hi - lo) / 3
if f(m1) < f(m2):
lo = m1 # m1 处更低，峰只可能在 m1 右边，砍掉 [lo, m1)
else:
hi = m2 # 否则峰在 m2 左边，砍掉 (m2, hi]
return (lo + hi) / 2 # 区间已经极短，取中点当答案
def ternary_max_int(lo, hi, f):
"""整数域三分：区间缩到只剩两三个数时暴力比较。"""
while hi - lo > 2: # 留 3 个数就收手：再缩下去取整会让区间不再变小
m1 = lo + (hi - lo) // 3
m2 = hi - (hi - lo) // 3
if f(m1) < f(m2):
lo = m1 + 1 # m1 已确定不是峰值点，可以连它一起排除
else:
hi = m2
return max(range(lo, hi + 1), key=f) # 最后 2–3 个候选直接比，顺带绕开平台段的坑
| 二分 | 三分 | |
|---|---|---|
| 前提 | 单调 | 单峰 |
| 每次区间缩到 | \(1/2\) | \(2/3\) |
| 迭代次数（同精度） | \(\log_2\) | \(\log_{1.5}\)，约 1.7 倍 |
| 严格性要求 | 无 | 必须严格单峰，有平台段会挂 |
有「平台段」（相邻值相等）时三分不可靠。整数域三分尤其容易踩， 稳妥做法是最后留 3–5 个候选点暴力比较，就像上面的
ternary_max_int。
44.6 二分的「隐身」形态¶
课件最后列了一串「其实也是二分」的东西，值得记住：
| 形态 | 说明 | 章节 |
|---|---|---|
| 二叉搜索树 / 线段树 | 每次砍掉一半区间 | 39-树状数组与线段树 |
| 倍增 | 从大到小试跳，本质是二进制拆分 | 45-倍增 |
| LIS 的 \(O(n\log n)\) 解法 | 在「各长度的最小结尾」数组上二分 | 102-线性DP |
| 高精度除法 | 二分商 | 22-高精度与大整数 |
| 整体二分 / CDQ | 对答案分治 | 118-分治进阶 |
| 分数规划 | 二分比值再判定 | — |
44.7 例题¶
BISHI85 【模板】整数域二分（简单）¶
\(n, q \le 2\times10^5\)，\(|a_i| \le 10^9\)。每次询问「数组中值在 \([l, r]\) 内的元素个数」。 题面见 BISHI85 原题（牛客）。
排序 + 两次 bisect 相减，44.1 那张表的直接应用：
import sys
from bisect import bisect_left, bisect_right
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = sorted(map(int, data[2:2 + n])) # bisect 的前提：有序
qs = list(map(int, data[2 + n:2 + n + 2 * q])) # 每个询问占 2 个 token
out = []
ap = out.append
for i in range(0, 2 * q, 2):
l = qs[i]; r = qs[i + 1]
# bisect_right(a, r) 是「第一个 > r 的下标」= 值 <= r 的元素个数
# bisect_left(a, l) 是「第一个 >= l 的下标」= 值 < l 的元素个数
# 两者相减即闭区间 [l, r] 内的元素个数
c = bisect_right(a, r) - bisect_left(a, l) # <= r 的个数 - < l 的个数
ap(c if c > 0 else 0) # 题面未保证 l <= r，负数时取 0 兜底
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
四个要点：
- 左边界用
bisect_left、右边界用bisect_right，这样两端都是闭区间。 两个都用bisect_left会漏掉等于 \(r\) 的元素——这是本题唯一的考点。 - 题面只说 \(-10^9 \le l, r \le 10^9\)，没保证 \(l \le r\)。
真出现 \(l > r\) 时两式相减会是负数，所以加一句
if c > 0 else 0兜底。 读数据范围时留意「有没有保证 \(l \le r\)」是一个好习惯。 - 手写二分在这里毫无意义：\(q = 2\times10^5\) 次查询，
bisect全在 C 层， 手写要多出 \(2\times10^5 \times 18\) 次 Python 循环。 - 若题目改成「带修改」，就该上树状数组了，见 39-树状数组与线段树。
BISHI87 [CQOI2010] 扑克牌（中等）¶
\(n\ (\le 50)\) 种牌，第 \(i\) 种有 \(c_i\) 张，另有 \(m\) 张 Joker。 一套牌 = \(n\) 种各一张，或 Joker + 其余 \(n-1\) 种各一张。求最多组几套。 \(c_i, m \le 5\times10^8\)。 题面见 BISHI87 原题（牛客）。
二分答案的教科书例题：直接构造很难，但「能不能组出 \(t\) 套」很好判。
固定 \(t\)，考察可行性：
- 每套牌里第 \(i\) 种最多用 1 张，所以第 \(i\) 种牌总共最多贡献 \(\min(c_i, t)\) 张；
- 每套牌最多用 1 张 Joker，所以 Joker 最多贡献 \(\min(m, t)\) 张；
- 总共需要 \(n \cdot t\) 张牌。
单调性：\(t\) 增大时左边最多线性增长（斜率 \(\le n\)），右边斜率恰好 \(n\)， 而每种牌迟早会被 \(\min\) 卡住，所以差值单调不增——可行性关于 \(t\) 单调。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
c = list(map(int, data[2:2 + n]))
def ok(t):
"""能否凑出 t 套牌。t 增大时左边最多线性增长、右边斜率恰为 n，故可行性单调。"""
if t == 0:
return True # 一套都不组永远可行，作为二分的下界锚点
s = 0
for x in c:
s += x if x < t else t # 每种牌在 t 套里最多用 t 张，多的用不上
return s + (m if m < t else t) >= n * t # 可用牌数 >= 需求 n*t
lo, hi = 0, (sum(c) + m) // n + 1 # 牌总数除以每套张数再 +1，这个 hi 一定不可行
# 求「最大的可行 t」= 44.2 写法二：mid 必须上取整，否则 hi == lo+1 时死循环
while lo < hi:
mid = (lo + hi + 1) // 2 # 求「最大的可行 t」-> mid 上取整
if ok(mid):
lo = mid # mid 可行，它自己可能就是最大值，保留
else:
hi = mid - 1 # mid 不可行，更大的更不可行
print(lo)
main()
- 用的是 44.2 的写法二（求最大可行解），所以
mid必须(lo + hi + 1) // 2。 写成下取整会在hi = lo + 1时死循环。 - 上界取 \(\lfloor(\sum c_i + m)/n\rfloor + 1\)：牌总数除以每套需要的张数， 再 \(+1\) 确保它不可行。上界给宽一点不会变慢（只多一两次迭代），给窄了会 WA。
min用条件表达式手写：x if x < t else t比min(x, t)略快， 因为省掉一次函数调用。\(n \le 50\) 时无所谓，但这个习惯在热循环里值钱。
BISHI88 小苯的魔法染色（中等）¶
长为 \(n\) 的
W/R串，最多施法 \(m\) 次，每次把一个长度 \(\le k\) 的区间全染红。 求能把所有W染红的最小 \(k\)。\(m \le n \le 2\times10^5\)。 题面见 BISHI88 原题（牛客）。
题面直接写着「求最小的 \(k\)」，且 \(k\) 越大越容易做到——单调性是显然的，二分答案。
check(k) 用贪心：从左往右扫所有 W，遇到没被覆盖的就在这里开一个长度为 \(k\) 的区间
（起点就放在这个 W 上，能覆盖到最右）。这样用的区间数最少。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
s = data[2]
pos = [i for i, ch in enumerate(s) if ch == 87] # 'W' 的 ASCII 码是 87
if not pos: # 没有白格，一次都不用施法
print(0)
return
def ok(k):
"""长度上限取 k 时，m 次施法够不够。k 越大越容易达成，所以可行性对 k 单调。"""
cnt = 0
cover = -1 # 已覆盖到的最右下标，-1 表示还没覆盖任何格
for i in pos:
if i > cover: # 这个 W 还露在外面，必须新开一个区间
cnt += 1
if cnt > m:
return False # 已超预算，后面不用再看了
cover = i + k - 1 # 起点压在这个 W 上，右端因此最远
return True
lo, hi = 1, n # 长度至少 1，至多 n（一次盖全串）
while lo < hi: # 求最小可行 k -> 写法一
mid = (lo + hi) // 2 # 下取整，配合 hi = mid 不会死循环
if ok(mid):
hi = mid # mid 够用，更小的还可能够
else:
lo = mid + 1 # mid 不够用，答案只可能更大
print(lo)
main()
- 贪心的正确性：区间起点放在当前最左未覆盖的
W上是最优的—— 再往左浪费长度，再往右就盖不住这个W。这是标准的区间覆盖贪心，见 47-贪心。 - 只遍历
W的位置而不是整个串：check从 \(O(n)\) 降到 \(O(|W|)\)， 总复杂度 \(O(|W|\log n)\)。 cnt > m立刻return False：这个剪枝在 \(k\) 很小时能省掉绝大部分工作。s是bytes，逐字节比较的是整数（'W'是 87）。 写ch == 'W'会永远为假——这是buffer.read()最常见的坑，见 20-输入输出处理。- 全
R时答案是 0，不是 1。 题面写着「输出一个正整数」， 但实测数据里存在全R的测试点，期望输出是 \(0\)——一次都不用施法。 这类「输出描述与真实数据不符」在牛客上并不罕见： 边界情形以数据为准，题面的措辞不能当成担保。 更麻烦的是这种错法只挂在一个分支上，二分主体完全正确， 很容易误判成二分写错而去反复改主循环。
BISHI89 山峰数组计数（中等）¶
把长为 \(n\) 的正整数数组切成三段（\(b_1, b_2, b_3\) 为三段和）， 求满足 \(b_1 < b_2 > b_3\) 的切法数。\(n \le 2\times10^5\)，\(P_i \ge 1\)。 题面见 BISHI89 原题（牛客）。
设前缀和 \(S\)，切点为 \(i < j\)，则 \(b_1 = S_i\)、\(b_2 = S_j - S_i\)、\(b_3 = S_n - S_j\)。 两个条件都能整理成「\(S_j\) 大于某个只与 \(i\) 有关的量」：
因为 \(P_i \ge 1\)，前缀和 \(S\) 严格递增——这就给了二分的前提。 枚举 \(i\)，二分出最小的合法 \(j\)，其后的 \(j\) 全部合法，一次算完：
import sys
from bisect import bisect_left
from itertools import accumulate
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# 前面补 0，下标偏移一位：pre[i] = P1 + .. + Pi，pre[0] = 0
pre = [0] + list(accumulate(map(int, data[1:1 + n]))) # pre[i] = P1+..+Pi
S = pre[n] # 全部元素之和
ans = 0
for i in range(1, n - 1): # i 是第一个切点，右边至少要留下 j 和第三段
x = pre[i]
low = 2 * x + 1 # S_j > 2 S_i，整数化成 >= 2S_i + 1
low2 = (S + x) // 2 + 1 # 2 S_j > S + S_i -> S_j >= ⌊(S+S_i)/2⌋+1
if low2 > low: # 两个下界取更严的那个
low = low2
# P_i >= 1 使 pre 严格递增，才有资格上 bisect；三、四参数限定 [i+1, n)，避开 O(n) 切片
j = bisect_left(pre, low, i + 1, n) # 在 pre[i+1 .. n-1] 里找第一个 >= low
if j <= n - 1:
ans += n - j # pre 递增，j 之后的 j 全部满足，一次性累加
print(ans)
main()
三个要点：
- 严格不等式的整数化：\(S_j > 2S_i\) 等价于 \(S_j \ge 2S_i + 1\)；
\(2S_j > S + S_i\) 等价于 \(S_j \ge \lfloor (S+S_i)/2 \rfloor + 1\)。
在整数域上，把「\(>\)」变成「\(\ge\) 某个整数」再交给
bisect_left， 是避免边界错误的最稳做法。 千万别用浮点除法。 bisect_left(pre, low, i + 1, n)的三、四参数限定了搜索区间 \([i+1, n)\)， 正好对应 \(j\) 的合法范围 \(i < j < n\)。这比切片pre[i+1:n]好——切片是 \(O(n)\) 复制。- 这题也可以用双指针（两个阈值都随 \(i\) 单调递增），\(O(n)\) 且更快。 这正是 44.3 末尾那句提醒的实例：二分是保底，不是唯一。
BISHI86 圆覆盖（中等）¶
平面上 \(n \le 10^5\) 个带权点，以原点为圆心放一个圆， 求使被覆盖点权值和 \(\ge S\) 的最小半径；无解输出 \(-1\)。 相对误差 \(10^{-6}\) 内算对。 题面见 BISHI86 原题（牛客）。
这题的正解是「二分的退化形态」：把点按到原点距离的平方 \(d_i = x_i^2 + y_i^2\) （整数！）排序，求权值前缀和，第一个前缀和 \(\ge S\) 的位置就是答案， 半径 \(= \sqrt{d}\)。
# [片段] 本题输出实数、官方为 special judge，未接入本地自动校验
import sys
from itertools import accumulate
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); S = int(data[1])
pts = []
for i in range(n):
# 每个点占 3 个 token（x, y, v），第 i 个点从下标 2 + 3i 开始
x = int(data[2 + 3 * i]); y = int(data[3 + 3 * i]); v = int(data[4 + 3 * i])
pts.append((x * x + y * y, v)) # 距离的平方，整数，不丢精度
pts.sort() # 按距离平方升序 = 按半径升序（平方在非负数上保序）
tot = 0
for d, v in pts:
tot += v # 半径扩到 d 时被覆盖的权值和
if tot >= S:
print("%.6f" % (d ** 0.5)) # 首次达标的位置就是答案，最后一步才开方
return
print(-1) # 全部点都覆盖仍不够，无解
main()
三条本章要强调的经验：
- 能用整数就别用浮点：比较距离时用 \(d = x^2+y^2\)，只在最后一步开方。
\(|x|, |y| \le 10^9\) 时 \(d\) 可到 \(2\times10^{18}\)，C++ 要
long long且要小心中间溢出， Python 的int无上限，直接算。 - 权值和 \(S \le 10^{14}\)，同样超 32 位，Python 无感。
- 半径本身要不要二分？不需要。 答案一定取在某个点的距离上（半径再小就少覆盖一个点）， 所以排序 + 前缀和一遍扫完，\(O(n\log n)\)，比「二分半径 + 每次 \(O(n)\) 统计」的 \(O(n\log V)\) 更快也更精确。这就是课件说的「验证方法足够优秀时就抛弃二分」。
若真要二分，模板是 44.4 的固定 100 次迭代版本，check(r) 统计 \(d_i \le r^2\) 的权值和。
本题的题解文件尚未建立，上面的代码未经本地样例自动校验（实数 + special judge）。
BISHI91 拼接木棍（中等）¶
\(n \le 60\) 根小木棍（长度 \(\le 50\)）由若干等长大木棍砍成，求大木棍的最小可能长度。 题面见 BISHI91 原题（牛客）。
这题被归到二分章，但它其实不满足二分的前提——这一点必须讲清楚。
设总长为 \(T\)，候选长度 \(L\) 必须满足 \(L \mid T\) 且 \(L \ge \max a_i\)。 「\(L\) 可行」关于 \(L\) 不单调：\(L=6\) 可行不代表 \(L=7\) 可行（\(7 \nmid T\) 时直接非法）， \(L\) 大也不一定更容易拼（约束是「恰好拼满」而非「不超过」）。 所以只能从小到大枚举 \(L\)，配搜索 + 剪枝验证，这是经典的 NOIP 1999《木棒》。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted((int(v) for v in data[1:1 + n]), reverse=True) # 长的优先，剪枝更强
total = sum(a) # 总长固定，等于「根数 × 大木棍长度」
used = [False] * n # used[i]：第 i 根小木棍是否已被占用
def dfs(L, target, done, cur, start):
"""L: 大木棍长度; target: 需要拼几根; done: 已拼好几根; cur: 当前这根已拼长度"""
if done == target:
return True # 全部拼完，成功
if cur == L:
return dfs(L, target, done + 1, 0, 0) # 拼满一根，从头开始下一根
prev = -1 # 本层上一次尝试过的长度，用于剪枝③
for i in range(start, n):
# 跳过：已用过 / 放进去会超长 / 与刚试过的那根等长（等长木棍完全等价）
if used[i] or cur + a[i] > L or a[i] == prev:
continue
used[i] = True
# start 传 i+1：同一根大木棍内部只按下标递增取，避免把同一组合枚举多次
if dfs(L, target, done, cur + a[i], i + 1):
return True
used[i] = False # 回溯，恢复现场
prev = a[i] # 剪枝③：同长度只试一次
if cur == 0 or cur + a[i] == L: # 剪枝④
break
return False
# 「可行」对 L 不单调，只能从小到大枚举：L 必须整除总长，且不小于最长的那根小木棍
for L in range(a[0], total + 1):
if total % L == 0 and dfs(L, total // L, 0, 0, 0):
print(L) # 从小到大枚举，第一个成功的就是最小值
return
main()
四个剪枝（少任何一个都会 TLE）：
| 剪枝 | 写法 | 理由 |
|---|---|---|
| ① 长度整除 | total % L == 0 |
拼不满就不可能 |
② 降序排序 + start 递增 |
sorted(..., reverse=True)、range(start, n) |
大的先放，失败得早；同一根内不重复枚举组合 |
| ③ 同长度只试一次 | a[i] == prev: continue |
长度相同的木棍等价 |
| ④ 首根 / 恰好填满失败即整体失败 | if cur == 0 or cur + a[i] == L: break |
当前根的第一根木棍放不进任何方案 ⟹ 该 \(L\) 无解；恰好填满还失败 ⟹ 后续更不可能 |
剪枝④是本题的灵魂：
cur == 0时，说明我们在为一根新的大木棍挑第一段。 若挑最长的那段都失败了，那它必须出现在某根大木棍里、且哪里都放不下， 整个 \(L\) 直接判死。这一条把搜索树砍掉了绝大部分。
搜索与剪枝的系统讲法见 62-记忆化搜索与剪枝。
44.8 本章速查¶
| 需求 | 做法 |
|---|---|
| 有序数组查找 | bisect，别手写 |
| 值在 \([l, r]\) 的个数 | bisect_right(a, r) - bisect_left(a, l) |
| 3.9 里按字段二分 | 先抽出关键字数组，bisect 无 key 参数 |
| 降序数组 | 存相反数转升序 |
| 最小的可行解 | while lo < hi: mid=(lo+hi)//2; check→hi=mid else lo=mid+1 |
| 最大的可行解 | while lo < hi: mid=(lo+hi+1)//2; check→lo=mid else hi=mid-1 |
| 死循环 | lo = mid 却用了下取整 mid |
mid 计算 |
Python 不会溢出，但必须用 // |
| 实数二分 | 固定 100 次迭代，不要 while hi-lo>eps |
| 实数能转整数 | 二分 \(r^2\) 而不是 \(r\) |
| 单峰求极值 | 三分，每次缩到 \(2/3\)；整数域末尾留几个点暴力 |
| 「最大值最小」 | 二分答案的信号词 |
check 的实现 |
贪心 / 前缀和 / DP / 数据结构 |
| 不满足单调性 | 不能二分，改枚举 + 剪枝搜索（BISHI91） |
bytes 逐字节比较 |
得到的是 int，ch == 'W' 恒假 |
| 模板 | 位置 |
|---|---|
| 四种整数二分边界 | §44.2 |
| 二分答案骨架 | §44.3 |
| 实数二分（固定迭代） | §44.4 |
| 三分（实数 / 整数） | §44.5 |