二分答案：猜一个再验一遍

猜一个答案再验一遍

上一课的二分是在有序数组里找一个值：数组已经摆在那儿，我们只要扔掉一半。

这一课的题目长得完全不一样。比如：有几根木头，要切出至少 K 段一样长的木段，每段最长能有多长？

直接算没有公式。但反过来问就容易多了：假如每段切成 7 长，够不够切出 K 段？ 这个问题只要把每根木头除以 7、把商加起来、和 K 比一比——扫一遍就完事。

于是换个思路：

• 别去求最优解，先猜一个答案。
• 再花一点代价验一验这个猜的答案行不行。
• 行，就往更「贪心」的方向猜；不行，就往回退。

那个「验一验」的函数习惯上叫 check。原来的问题叫最优化问题（求最大/最小），新的问题叫判定问题（问行不行）。二分答案的价值就在这一步转换：把「怎么求最好」换成「这样行不行」——后者通常好写得多。

木头能切多长

照着这个思路写出来：

def check_wood(woods, length, K):
    """切出 length 这么长的段，够不够 K 段。"""
    total = 0
    for x in woods:
        total += x // length
    return total >= K


def solve_wood(woods, K):
    lo, hi = 1, max(woods)
    while lo <= hi:
        mid = (lo + hi) // 2
        if check_wood(woods, mid, K):
            lo = mid + 1          # 能切出来，试试更长的
        else:
            hi = mid - 1          # 切不出来，往短了试
    return hi


woods = [10, 10, 10]
print('  每段最长:', solve_wood(woods, 3))
print('  每段最长:', solve_wood(woods, 7))

  每段最长: 10
  每段最长: 3

三根 10 长的木头要切 3 段，每段最长 10。要切 7 段，每段最长 3——每根各切 3 段共 9 段，够 7 段；再长一点到 4，每根只切得出 2 段、共 6 段，不够了。这个「4 不行、3 行」的界，正是 check 去判的事。

check 里那个 total >= K 是判定的核心。注意它是单调的：段长要求得越短，越容易切够。所以「能不能切够」这个判断随着 length 从小到大一定是从「能」变成「不能」，中间不会有反复。有这个性质，二分才成立。

跳石头

再看一道。一条河从起点到终点长 L，河里有 N 块石头，最多能搬走 M 块，问搬完之后最短的那一跳最长能有多长。

这也是「最大中的最小」：要让所有跳跃距离的最小值尽可能大。同样先写 check：假如要求每一跳都不小于 d，最少要搬走几块石头？ 这个能用贪心扫一遍算出来——从头开始走，遇到一块石头离上一块不足 d，就把它搬走。

def check_jump(stones, L, d, M):
    """最短跳跃距离不小于 d，需要搬走几块石头。"""
    removed = 0
    prev = 0
    for s in stones:
        if s - prev < d:
            removed += 1
        else:
            prev = s
    if L - prev < d:
        removed += 1
    return removed <= M


def solve_jump(stones, L, M):
    lo, hi = 1, L
    while lo <= hi:
        mid = (lo + hi) // 2
        if check_jump(stones, L, mid, M):
            lo = mid + 1
        else:
            hi = mid - 1
    return hi


print('  答案:', solve_jump([2, 11, 14, 17, 21], 25, 2))

  答案: 4

河长 25，石头在 2、11、14、17、21，搬走 2 块之后最短的一跳最长是 4。搬走 2 和 14，剩下 0、11、17、21、25：跳跃距离是 11、6、4、4、4，最短 4。

两道题的骨架一模一样，差别只在 check 里面。这就是二分答案的通用形状：一个 check，一个二分主体，换题只换 check。

check 必须单调

上面两题的 check 都是单调的。如果它不是呢？

二分的前提是「扔掉的那一半真的可以扔」。所以判定结果必须长成这个样子：

一旦出现「能 不能 能」这种反复，二分每次扔掉一半就可能在扔掉的半边里丢掉真正的答案。

把这个性质人为破坏掉看一看。条件改成「长度是偶数且不超过 8」，可行的长度是 2、4、6、8，真正的最大值是 8：

def check_broken(length):
    return length % 2 == 0 and length <= 8


def solve_broken(lo, hi):
    while lo <= hi:
        mid = (lo + hi) // 2
        if check_broken(mid):
            lo = mid + 1
        else:
            hi = mid - 1
    return hi


for lo, hi in [(1, 20), (1, 16), (1, 10), (1, 9), (1, 8), (5, 20)]:
    got = solve_broken(lo, hi)
    print(f'  区间 [{lo:>2}, {hi:>2}] -> 交回 {got:>2}   这个值可行吗 {check_broken(got)}')

  区间 [ 1, 20] -> 交回  2   这个值可行吗 True
  区间 [ 1, 16] -> 交回  8   这个值可行吗 True
  区间 [ 1, 10] -> 交回  2   这个值可行吗 True
  区间 [ 1,  9] -> 交回  2   这个值可行吗 True
  区间 [ 1,  8] -> 交回  6   这个值可行吗 True
  区间 [ 5, 20] -> 交回  8   这个值可行吗 True

同一段二分代码、同一个条件，只把初始区间从 [1,20] 换成 [1,16]，答案就从 2 变成 8。

更麻烦的是「这个值可行吗」那一列全是 True。也就是说拿到错的答案（2）时，你没法靠「验一验它行不行」发现问题——它确实行，只是远不是最大的。真正最大值是 8。

所以「二分答案」这道菜的第一步不是写二分，而是先确认 check 单调。确认的办法是问自己一句：「如果长度 d 可以，那么比 d 短的呢？」答不上来，就不该用二分。

答案区间怎么定

二分的两个边界 lo 和 hi 要框住答案。框错了有两种后果。

第一种：上界取小了。 还是木材加工，两根 100 长的木头要切 2 段，答案明明是 100；如果上界只取 50，二分老老实实交回 50：

def solve_with_hi(woods, K, hi):
    lo = 1
    while lo <= hi:
        mid = (lo + hi) // 2
        total = 0
        for x in woods:
            total += x // mid
        if total >= K:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi


print('  上界取 100:', solve_with_hi([100, 100], 2, 100))
print('  上界取  50:', solve_with_hi([100, 100], 2, 50))

  上界取 100: 100
  上界取  50: 50

上界取小了不会报错，只会安静地给出一个偏小的答案。 取上界的规矩是「宁可大得离谱」：答案最大可能是什么？把木头全长当成一段、把河长当成一跳，都是安全的。

第二种：收缩方向配错了取整方式。 要取「最大的可行值」时，循环里是 lo = mid 这种不往前挪一格的写法。这时如果 mid 用向下取整 (lo + hi) // 2，程序会卡死：

def ok(x):
    return x <= 8


def solve_infinite(step_cap=20):
    lo, hi = 1, 20
    steps = 0
    while lo < hi:
        steps += 1
        if steps > step_cap:
            return lo, hi, True
        mid = (lo + hi) // 2          # 向下取整
        if ok(mid):
            lo = mid                  # 不往前挪
        else:
            hi = mid - 1
    return lo, hi, False


lo, hi, looped = solve_infinite()
print(f'  向下取整：卡在 lo={lo} hi={hi}，还在循环里 {"是" if looped else "否"}')

  向下取整：卡在 lo=8 hi=9，还在循环里 是

lo=8, hi=9 时 mid 永远是 8，ok(8) 为真于是 lo 又变回 8——一步都没动，死循环。把取整改成向上就通了：

def solve_right():
    lo, hi = 1, 20
    steps = 0
    while lo < hi:
        steps += 1
        mid = (lo + hi + 1) // 2      # 向上取整
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo, steps


ans, steps = solve_right()
print(f'  向上取整：答案 {ans}，用了 {steps} 步')

  向上取整：答案 8，用了 4 步

记法：收缩时写 lo = mid 就配向上取整 (lo + hi + 1) // 2；写 lo = mid + 1 就配向下取整。 上一课的二分模板全用 mid + 1 和 mid - 1，所以那边不用管取整方向——两套模板别混着抄，混了就是这里出问题。

check 不能太慢

二分只查 O(\log(\text{答案范围})) 次，但每次 check 的代价要乘上去。

（本机实测，与 \log_2 完全对上：\log_2 10^9 = 29.9。）

这个表是二分答案最好用的地方：答案范围从一千涨到一万亿，check 次数只从 9 涨到 40。 所以答案范围大得离谱不用怕。

真正的风险在 check 自己。n 个元素、答案范围 10^9，总复杂度是 O(n \log 10^9) = O(30n)——很宽裕。但如果 check 里塞了个排序：

（本机实测，只多了一次 sorted 就慢 2.6 倍。）

一次 sorted 只是 2.6 倍，还能忍。但 check 里如果套了个 O(n^2) 的双重循环，就是 \times 200000——直接超时。规矩：check 里最多一次 O(n) 扫描，或者一次 O(n \log n) 排序加一次扫描。 想放两个循环，先想想能不能合并成一个。

二分答案与二分查找

两者都叫二分，形状也像，但问的东西不一样：

• 二分查找（第 14 课）：在一个已经有序的数组里找一个值的位置。每次比的是「中间这个数和目标谁大」。
• 二分答案（这一课）：在一个答案的取值范围里找最优值。每次比的是「这个猜测值行不行」。

一句更直白的话：二分查找的「有序」是题目给你的，二分答案的「单调」是你要去证的。

这一课用到的判断

• 二分答案的第一步是转换：把「求最大/最小」换成「这个值行不行」。判定问题一般比最优化问题好写得多。
• check 必须单调：随参数从小到大，判定结果只能是从真到假一趟，不能反复。
• 单调性不成立时二分不会报错，只会给出一个乱跳的答案：实测同一段代码、同一个条件，初始区间换成 [1,16] 答案就从 2 变成 8，而两个答案都是可行的，你验不出来。
• check 里最多一次 O(n) 扫描（或一次排序加一次扫描）；塞进 O(n^2) 就是 \times n 的灾难。
• 二分次数只跟答案范围的对数有关：范围从 10^3 涨到 10^{12}，次数只从 9 涨到 40。范围大不用怕，check 慢才可怕。
• 上界宁可取大：答案最大可能是多少，就往那儿取（木头全长、河长）。取小了不报错，只给偏小的答案。
• 收缩写 lo = mid 就要配向上取整 (lo + hi + 1) // 2；写 lo = mid + 1 配向下取整。两套模板别混抄，混了要么死循环要么差一。
• 别把二分查找的模板直接搬过来：那边二分的是下标、判断靠比大小，这边二分的是答案、判断靠 check。

• 洛谷 P2678 跳石头二分答案的经典题，本课第二节的题目
• OI Wiki · 二分二分查找与二分答案的统一下界/上界写法
• 《算法导论（第 3 版）》第 2 章 2.3 分治法的设计书 · 二分的思想与循环不变式
• 第 14 课：二分：每次砍掉一半上一课二分的是数组下标，这一课二分的是答案取值