# 0022 · 二分答案：猜一个再验一遍 · 参考解

二分答案只有一个动作：**写 check 函数检查「行还是不行」，然后在答案范围里二分猜**。
四个任务把这个模式拆成四种场景：

```text
木材切割        —— check = 够不够段数       —— 最标准的二分答案
跳石头          —— check = 能不能移掉石头    —— 答案也是距离
暴力验算        —— 暴力枚举验证二分答案正确  —— 200+ 组对拍
破坏单调性      —— 不单调会导致结果漂移      —— 依赖初始区间
```

| 任务 | 文件 | 要交的东西 |
| --- | --- | --- |
| 1 · 木材切割 | `task01_wood_cutting.py` | `check_wood` / `max_wood_length` |
| 2 · 跳石头 | `task02_river_hopping.py` | `check_jump` / `max_min_gap` |
| 3 · 暴力验算 | `task03_bruteforce_verify.py` | `brute_max_wood_length` / `verify_on_random_data` |
| 4 · 破坏单调性 | `task04_break_monotonicity.py` | `check_bad` / `binary_search_on_answer` / `brute_best` |

把这一份里的文件拷进你的任务目录就能直接跑（`tools.py`、`run_tests.py` 与 `probes/` 两侧内容完全相同）：

```text
py run_tests.py        # 在 solutions/0022-binary-search-on-answer/ 目录里直接跑
```

参考解的判分结果：**全部 PASS / 0 FAIL、退出码 0**。留白版是大量 FAIL，每条 FAIL 都点名要改的 TODO。

## 逐题：为什么这么写

### 任务 1 · 木材切割

`check_wood(woods, x, M)` 做的事：遍历每根木头，看能切出多少段长度为 x 的。`w // x` 就是这根木头能切出的段数（整数除法自动扔掉余数）。总和 ≥ M 就说明 x 可行。

二分答案模板（上取整）：
```
lo = 1, hi = max(woods)
while lo < hi:
    mid = (lo + hi + 1) // 2      # ← 上取整，防 lo=hi-1 时死循环
    if check(mid):  lo = mid      # 可行 → 往大猜
    else:           hi = mid - 1  # 不可行 → 往小猜
return lo
```

| 数据 | M=3 | M=6 | M=9 | M=15 |
| --- | --- | --- | --- | --- |
| [10,10,10] | 10 | 5 | 3 | 2 |

M 越大，长度越小——单调性完整。

### 任务 2 · 跳石头

`check_jump(stones, river_len, min_gap, remove_limit)` 做的事：从起点 0 出发，依次检查每块石头。如果当前石头和前一个落脚点的间距小于 min_gap，就把这块石头移掉（removed++）。否则落脚到这块石头上。最后一段（到终点 river_len）也必须 ≥ min_gap。

课件数据验证：

| min_gap | 移除 0 块 | 移除 1 块 | 移除 2 块 | 移除 3 块 |
| --- | --- | --- | --- | --- |
| 最大可行 | 2 | 2 | 4 | 11 |

移除越多石头，能实现的最小间距越大——这也是单调的。

### 任务 3 · 暴力验算

暴力枚举从 `max(woods)` 往下查到 1，找到第一个 check 返回 True 的。这是"真·答案"。

在 200 组随机小数据上（木材长度 ≤ 60），暴力与二分答案**全部一致**——说明 check 函数是单调的时，二分答案正确。

### 任务 4 · 破坏单调性

`check_bad(x)` 的 True 区间是 {2, 4, 6, 8}——偶数且 ≤ 8。这不是从 1 开始的连续区间，所以不单调。

二分答案在上取整版本中的行为：

| 初始区间 | 二分找到 | 暴力枚举（真·答案） | 一致？ |
| --- | --- | --- | --- |
| [1, 20] | 8 | 8 | 一致 |
| [1, 10] | 8 | 8 | 一致 |
| [1, 8] | 8 | 8 | 一致 |
| [1, 5] | 4 | 4 | 一致 |
| [3, 10] | 8 | 8 | 一致 |
| [5, 20] | 6 | 8 | 不一致 |

`[5, 20]` 区间上二分找到 6 而不是 8——因为 check_bad(5) = False, hi 降到 4, lo=5>hi, 最终从 lo=5 开始二分... 实际上让我们详细看看：

[5, 20]: lo=5, hi=20
- mid=(5+20+1)//2=13. check_bad(13)=False (奇数). hi=12.
- mid=(5+12+1)//2=9. check_bad(9)=False (奇数). hi=8.
- mid=(5+8+1)//2=7. check_bad(7)=False (奇数). hi=6.
- mid=(5+6+1)//2=6. check_bad(6)=True (偶数≤8). lo=6.
- lo=6, hi=6 → return 6.

二分找到 6。暴力从 20 往下枚举：20(F),19(F),...,8(T) → 返回 8。不一致！

这就是单调性被破坏的结果：**二分答案找到的不再是全局最大值，而是「二分路径上第一个遇到的峰值」**。

## 常见错法（判分逐条盯着）

| 错法 | 会看到什么 |
| --- | --- |
| check 函数忘了 `w // x` | 全部返回 False 或 0 |
| 二分 mid 忘了上取整 | lo=hi-1 时死循环 |
| check_jump 忘了检查最后一段 | min_gap 过大时也返回 True |
| 暴力枚举从 1 往上查 | 找到最小值而不是最大值 |
| check_bad 忘了同时检查偶数和 ≤8 | 不单调性体现不出来 |

## 判分在读什么

- **四个任务各起一个进程跑**，只看 stdout 里的固定格式行，不 import 学生代码；
- **木材切割靠对拍验**：check 函数四组 + 二分答案三组 + 全部 M 值 + 边界数据；
- **跳石头靠对拍验**：check 函数三组 + 二分答案三组 + 0~5 移除数扫描 + 边界；
- **暴力验算靠对拍验**：200+ 组随机数据上二分与暴力全部一致；
- **单调性破坏比较**：不同初始区间的二分结果与暴力结果对比；
- **一条耗时判据都没有**。