# 二分与三分算法（Binary & Ternary Search）

二分与三分是计算机科学中极具降维打击色彩的搜索算法。它们通过对单调性或单峰（谷）性的判定，每次排除掉一定比例的搜索空间，将原本需要线性扫描的开销直接降至对数级别，是解决最优化问题的核心手段。

---

## 1. 二分查找的思想本质

### 1.1 猜数游戏的直觉
假设我们玩一个猜数游戏：我心里想一个 $1$ 到 $1000$ 之间的整数，你来猜。每次我只会告诉你“猜小了”或“猜大了”。
* **线性查找**：若从 $1$ 开始挨个猜，最坏情况下要猜 $1000$ 次。
* **对半折半**：若你第一次猜 $500$，若我说“小了”，范围缩至 $[501, 1000]$；若说“大了”，范围缩至 $[1, 499]$。无论结果如何，你都**排除了一半的可能性**。持续折半，最多只需 $\log\_2 1000 \approx 10$ 次猜数即可锁定答案。

这就是二分的直觉来源：通过判断中点状态，每次可靠地排除半数搜索空间，以对数时间复杂度极速逼近目标。

---

### 1.2 核心基石：单调性与判定条件
二分查找并非只能用在“排好序的数组里找数”。二分能生效的本质，是**判定条件的单调性（Monotonicity）**。

设判定函数为 $\text{check}(x)$。若存在一个临界点 $ans$，使得当 $x$ 在 $ans$ 左侧时 $\text{check}(x)$ 恒为假（False），在右侧时恒为真（True），则 $\text{check}(x)$ 对 $x$ 具有单调性。
这意味着真假值序列呈现 $\text{F, F, \dots, F, T, T, \dots, T}$ 或 $\text{T, T, \dots, T, F, F, \dots, F}$ 的形态。
二分的目标就是**精确定位 F 与 T 的分界点**。
* **例 1**：在升序数组 $a$ 中寻找首个不小于 $v$ 的元素。判定条件为 $a[i] \ge v$，具有单调性。
* **例 2**：求解方程 $f(x) = C$（$f(x)$ 递增）。判定条件 $\text{check}(x)$ 设为 $f(x) \ge C$，同样具有单调性。

---

### 1.3 搜索空间 $[l, r]$ 的精确界定
* **闭区间 $[l, r]$**：表示 $l$、$r$ 及其之间所有的值均为潜在候选解。整数二分最常采用此定义。
* **半开区间 $[l, r)$**：表示候选解范围在 $l$ 到 $r-1$ 之间，$r$ 本身不含。
* 初始状态下，$l$ 和 $r$ 的边界必须完全覆盖所有可能的合法解，若设定的边界范围太窄，会直接遗漏真解。

---

## 2. 整数域上的二分搜索

整数二分的核心在于：中点 `mid` 的计算、左右边界的更新策略以及循环终止条件，这三者必须协同一致，否则极易陷入越界或死循环。

### 2.1 记录答案型模板（推荐，闭区间 $[l, r]$ 且维护 `ans`）
该模板结构清晰，多设置一个 `ans` 变量记录合法候选解，可以有效避免边界退化造成的死循环，极其推荐初学者与竞赛选手作为首选。

#### 模式 (1)：查找第一个使 $\text{check}(x)$ 为真的 $x$ (首个 $\text{T}$ 点)
真假值序列分布为：$\text{F, F, \dots, F, [T], T, \dots, T}$
```cpp
// 目标：寻找最小的 x (L <= x <= R)，使得 check(x) 为真
long long find_first_true(long long L, long long R) {
    long long l = L, r = R;
    long long ans = R + 1; // 哨兵值：初始化为上界外，代表可能无解
    while (l <= r) {
        long long mid = l + (r - l) / 2; // 防溢出的向下取整计算
        if (check(mid)) {
            ans = mid;    // mid 是当前合法候选解，记录
            r = mid - 1;  // 尝试在左半区间 [l, mid - 1] 寻找更小的解
        } else {
            l = mid + 1;  // mid 不满足条件，解必在右半区间 [mid + 1, r]
        }
    }
    return ans;
}
```

#### 模式 (2)：查找最后一个使 $\text{check}(x)$ 为真的 $x$ (最后一个 $\text{T}$ 点)
真假值序列分布为：$\text{T, T, \dots, [T], F, F, \dots, F}$
```cpp
// 目标：寻找最大的 x (L <= x <= R)，使得 check(x) 为真
long long find_last_true(long long L, long long R) {
    long long l = L, r = R;
    long long ans = L - 1; // 哨兵值：初始化为下界外
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;    // mid 是合法候选解，记录
            l = mid + 1;  // 尝试在右半区间 [mid + 1, r] 寻找更大的解
        } else {
            r = mid - 1;  // mid 不满足条件，解必在左半区间 [l, mid - 1]
        }
    }
    return ans;
}
```

---

### 2.2 收敛型模板（边界直接收缩）
该模板不依赖额外的记录变量 `ans`，而是通过区间 $[l, r]$ 的不断收缩判定，最终使 $l$ 与 $r$ 重合即为答案。

#### 模式 (1)：查找第一个使 $\text{check}(x)$ 为真的 $x$ (区间收敛到首个 $\text{T}$ 点)
```cpp
// 目标：在 [L, R] 内寻找满足条件的最小 x
long long find_first_true_收敛(long long L, long long R) {
    long long l = L, r = R + 1; // 搜索区间设计为左闭右开 [l, r)
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;     // mid 可能是解，答案在 [l, mid]
        } else {
            l = mid + 1; // mid 不是解，答案在 [mid + 1, r)
        }
    }
    return l; // 最终 l == r 便是所求点，若无解会收敛到 R + 1
}
```

#### 模式 (2)：查找最后一个使 $\text{check}(x)$ 为真的 $x$ (区间收敛到最后一个 $\text{T}$ 点)
```cpp
// 目标：在 [L, R] 内寻找满足条件的最大 x
long long find_last_true_收敛(long long L, long long R) {
    long long l = L, r = R;
    while (l < r) {
        // 特别注意：此处 mid 必须向上取整，否则当 r = l + 1 且 check(l) 成立时
        // mid 算出来依然等于 l，执行 l = mid 会导致 l 无法移动，陷入死循环
        long long mid = l + (r - l + 1) / 2; 
        if (check(mid)) {
            l = mid;     // mid 可能是解，区间缩为 [mid, r]
        } else {
            r = mid - 1; // mid 不是解，区间缩为 [l, mid - 1]
        }
    }
    return l; // 最终重合，可能为解，需在外部进行二次合法性校验
}
```

---

### 2.3 边界条件与避坑指南
1. **防止整型加法溢出**：不要写成 `mid = (l + r) / 2`。当 $l$ 和 $r$ 的和超出整型上限时会导致计算错误，应当写成：
   $$\text{mid} = l + \frac{r - l}{2}$$
2. **死循环成因**：收敛型模板中，若是向左（减小）收缩且采用向下取整时，容易因不位移产生死循环。必须牢记：**若在 check 成立时令 `l = mid`，计算 `mid` 时必须向上取整 `l + (r - l + 1) / 2`**。

---

### 2.4 典型示例：排序数组查找与二分界限（std::lower_bound 模拟）
* **题意**：给定升序数组 $a$ 和目标值 $v$，求 $v$ 的首次出现位置和出现次数。
* **原理**：
  * **首次出现位置**：即满足 $a[i] \ge v$ 的首个位置（对应 `lower_bound`）。
  * **首次大于其的位置**：即满足 $a[i] > v$ 的首个位置（对应 `upper_bound`）。

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
int a[N];
int n;

// 模拟 lower_bound: 查找第一个 >= v 的位置
int lb(int v) {
    int l = 0, r = n; // 区间 [0, n)，n 为哨兵代表无解
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= v) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 模拟 upper_bound: 查找第一个 > v 的位置
int ub(int v) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > v) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    n = 7;
    int tmp[] = {2, 5, 5, 5, 8, 10, 12};
    for (int i = 0; i < n; ++i) a[i] = tmp[i];
    
    int v = 5;
    int first_pos = lb(v);
    int upper_pos = ub(v);

if (first_pos < n && a[first_pos] == v) {
        cout << "首次出现位置: " << first_pos << "\n";
        cout << "总出现次数: " << upper_pos - first_pos << "\n";
    } else {
        cout << "元素不存在\n";
    }
    return 0;
}
```

---

### 2.5 经典例题：CF1352C - K-th Not Divisible by n
* **题意**：给定 $n$ 和 $k$，求出第 $k$ 个不能被 $n$ 整除的正整数。
* **分析**：
  设 $f(x)$ 为区间 $[1, x]$ 内不能被 $n$ 整除的数的个数：
  $$f(x) = x - \lfloor \frac{x}{n} \rfloor$$
  因为 $f(x)$ 随着 $x$ 增加具有明显的单调递增性。我们要寻找最小的 $x$ 使满足：
  $$f(x) \ge k$$
  这完美对应了“寻找第一个使检测条件为真的 $x$”模型。

```cpp
#include <iostream>
using namespace std;

long long n, k;

// 判定函数：前 v 个数内，不能被 n 整除的数是否达到了 k 个
bool check(long long v) { 
    return v - v / n >= k; 
}

void solve() {
    cin >> n >> k;
    long long l = 1, r = 2e9 + 7; // 设置一个安全且足够大的右界
    long long ans = r;
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试向左逼近更小的值
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}
```

---

## 3. 实数域（浮点数）二分搜索

实数二分无偏位对齐和边界退化取整问题。当答案在实数域内连续分布时，我们仅需要找到在**满足特定精度误差 `eps`** 约束下的近似解。

### 3.1 核心机制
* **精度控制手段**：
  * **循环判定控制精度**：`while (r - l > eps)`。使用该手段必须极度小心精度限制，若 `eps` 选得过小，由于浮点精度表示存在缺陷会导致陷入死循环。
  * **固定循环迭代次数**：**最稳健、最推荐的做法**。直接强制迭代 100 次。
    因为经过 $100$ 次折半拆分，搜索范围会被缩减到原始空间的 $2^{-100} \approx 10^{-30}$，可以绝对覆盖绝大多数竞赛题目的精度要求，甚至在部分由于运算可能产生负相关的极端用例下也绝不会产生死循环。

---

### 3.2 实数二分模板（固定迭代 100 次）
```cpp
// 寻找最小的 x 使得 check(x) 成立
double float_binary_search(double L, double R) {
    double l = L, r = R;
    for (int i = 0; i < 100; ++i) { // 强力循环迭代 100 次
        double mid = l + (r - l) / 2.0;
        if (check(mid)) {
            r = mid; // 答案在 [l, mid]
        } else {
            l = mid; // 答案在 [mid, r]
        }
    }
    // 当迭代完毕，l 和 r 极度逼近。寻找最小真值点，上界 r 比下界 l 更稳健
    return r;
}
```

---

### 3.3 典型示例：求解方程 $x^P = V$（求实数开根）
* **题意**：给定非负实数 $V$ 与正实数 $P$，求解 $x$ 使得 $x^P = V$。

```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

double v, p;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(10);
    
    v = 27.0; p = 3.0; // 计算 27.0 的三次方根
    double l = 0.0, r = max(1.0, v); // 初始化安全右边界
    
    for (int i = 0; i < 100; ++i) {
        double mid = l + (r - l) / 2.0;
        if (pow(mid, p) >= v) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << "\n"; // 输出: 3.0000000000
    return 0;
}
```

---

## 4. 二分答案（Binary Search on Answers）

答案二分是将“求一个最优值”这一极具策略和动态变数的最优化问题，巧妙逆向映射、降维为**一连串只需判定“可行或不可行”的判定性问题**的技巧。

### 4.1 核心思想
若所求的最终最优答案满足单调性：
* **求最小值的最大化**（对应 $\text{T, T, \dots, T, F, F, \dots, F}$）：寻找最右侧合法点。
* **求最大值的最小化**（对应 $\text{F, F, \dots, F, T, T, \dots, T}$）：寻找最左侧合法点。
我们就可以直接对“答案的值”建立二分空间 $[l, r]$，每次猜测一个值 $mid$，并通过 $\text{check}(mid)$ 检验该答案在物理条件上是否存在解。

---

### 4.2 典型例题一：CF165B - Burning Midnight Oil
* **题意**：写一本书共 $n$ 行代码。首轮写 $v$ 行，下一轮衰减为 $\lfloor v / k \rfloor$，再下一轮 $\lfloor v / k^2 \rfloor$，直至变为 $0$。求能完成任务的最小初始值 $v$。
* **分析**：
  初始值 $v$ 越低，能写的代码总行数 $S$ 越少。
  存在单调性：若某个 $v$ 成立，则所有 $> v$ 的值必然也成立。目标是寻找满足条件的最小 $v$，属于“最大值的最小化”（寻找首个 $T$）。

```cpp
#include <iostream>
using namespace std;

long long n, k;

// check 函数：初始写 v 行，代码总量是否能满足 n 行
bool check(long long v) {
    long long sum = 0, cur = v;
    while (cur > 0) {
        sum += cur;
        if (sum >= n) return true;
        cur /= k;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> k)) return 0;

long long l = 1, r = n, ans = n;
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试在左半段探测是否有更小的值
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}
```

---

### 4.3 典型例题二：CF812C - Sagheer and Nubian Market
* **题意**：
  有 $n$ 件商品，第 $i$ 件的基础价格为 $a\_i$。如果总共购买 $k$ 件物品，则第 $i$ 件商品的价格变更为 $a\_i + i \times k$。当前预算为 $S$。求在预算充裕的前提下最多能买多少件商品，以及此时对应的最小总开销。

* **分析**：
  可购买商品数 $k$ 具有完美的单调性。若能买 $k$ 件，则购买 $k-1$ 件必然可实现。目标是**最大化 $k$**（寻找最后一个 $T$）。
  * **$\text{check}(k)$ 的实现**：
    当确定购买数 $k$ 时，我们直接计算各商品对应的价格 $b[i] = a[i] + i \times k$，对其进行排序并选择最便宜的前 $k$ 个，检验其和是否在预算 $S$ 之内即可。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
int n;
long long s;
long long a[N];
long long b[N]; // 临时价格计算存储器

pair<bool, long long> check(int k) {
    if (k == 0) return {true, 0};
    for (int i = 0; i < n; ++i) {
        b[i] = a[i] + (long long)(i + 1) * k; // 商品下标 1-indexed
    }
    sort(b, b + n); // 贪心选取最便宜的
    long long sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += b[i];
    }
    return {sum <= s, sum};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> s)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

int l = 0, r = n;
    int ans_k = 0;
    long long ans_cost = 0;

while (l <= r) {
        int mid = l + (r - l) / 2;
        if (mid == 0) {
            l = mid + 1; continue;
        }
        auto res = check(mid);
        if (res.first) {
            ans_k = mid;
            ans_cost = res.second;
            l = mid + 1; // 尝试去买更多件
        } else {
            r = mid - 1;
        }
    }
    cout << ans_k << " " << ans_cost << "\n";
    return 0;
}
```

---

## 5. 进阶：二分答案与 0-1 分数规划（Fractional Programming）

0-1 分数规划是指用于优化形如“多项式比率”一类的特殊极值问题：
$$\text{Maximize/Minimize} \quad R(x) = \frac{\sum\_{i=1}^n a\_i \cdot x\_i}{\sum\_{i=1}^n b\_i \cdot x\_i} \quad (x\_i \in \{0, 1\})$$

### 5.1 判定问题转换推导
由于比率极其不便在状态转移时直接累加，我们采用**答案二分**。
以最大化比率为例，猜测一个比率 $ans$。若存在一种可行解方案使其比率不低于 $ans$，则有：
$$\frac{\sum a\_i x\_i}{\sum b\_i x\_i} \ge ans$$

假定分母大于零（通常代表总重量/总量在实际场景中非空），通过去分母变形：
$$\sum a\_i x\_i \ge ans \cdot \sum b\_i x\_i \implies \sum (a\_i - ans \cdot b\_i) \cdot x\_i \ge 0$$

令元素的新价值（权值）为：
$$d\_i = a\_i - ans \cdot b\_i$$
问题转化为：**是否存在一种选择方案，满足特定约束的前提下，使选择的新权值和非负：$\sum d\_i x\_i \ge 0$**。

---

### 5.2 经典例题：洛谷 P4377 [USACO18OPEN] Talent Show G
* **题意**：
  有 $N$ 头牛，第 $i$ 头重量为 $w\_i$，才艺值为 $t\_i$。我们需要从中挑选若干头牛组成战队。要求所挑牛的总重量不少于 $W$。目标是**最大化：(总才艺值) / (总重量)**。

* **题解核心**：
  二分最终比率 $ans$。构造新价值 $d[i] = t[i] - ans \times w[i]$。
  问题转化为：在挑出的牛“总重量至少为 $W$”的前提下，**最大化新价值的总和 $\sum d[i]$ 是否大于或等于 0**。
  这是一个经典的**0-1 背包最优化问题**。
  * **DP 状态设计**：
    `dp[j]` 表示当前选取牛的“总重量至少为 $j$”时的最大价值。
    $$dp[\min(W, j + w\_i)] = \max(dp[\min(W, j + w\_i)], dp[j] + d\_i)$$

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 255, W_MAX = 1005;
int n, w0;
int w[N], t[N];
double d[N];
double dp[W_MAX];

bool check(double ans) {
    for (int i = 1; i <= n; ++i) {
        d[i] = (double)t[i] - ans * w[i];
    }
    for (int i = 1; i <= w0; ++i) dp[i] = -1e18; // 初始化为极小值
    dp[0] = 0;

for (int i = 1; i <= n; ++i) {
        for (int j = w0; j >= 0; --j) {
            int nxt = min(w0, j + w[i]); // 超过总量限制均归并至 w0 处
            dp[nxt] = max(dp[nxt], dp[j] + d[i]);
        }
    }
    return dp[w0] >= 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> w0)) return 0;
    for (int i = 1; i <= n; ++i) cin >> w[i] >> t[i];

double l = 0, r = 1005.0; // 极值上界估算
    for (int i = 0; i < 100; ++i) {
        double mid = l + (r - l) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << (long long)(l * 1000) << "\n"; // 按题意乘以 1000 并向下取整
    return 0;
}
```

---

## 6. 进阶：二分与图论结合

### 6.1 二分 + 0-1 BFS 最短路问题
当判定条件需要验证连通性，或需要解一条带有权值瓶颈的特定路径时，我们将二分答案与图论算法深度结合。

#### 6.2 经典例题：洛谷 P1948 [USACO08JAN] Telephone Lines S
* **题意**：
  一个无向带权图，包含 $N$ 个节点、$P$ 条边。现在可以任意指定 $K$ 条边免费（权值清 0）。
  求在挑选出的所有连接 $1$ 到 $N$ 的路径中，**剩下的最贵收费边的最小可能值是多少**。

* **分析**：
  我们需要寻找一个最小的收费阈值 $lim$，使得存在一条从 $1$ 到 $N$ 的路径，其中**权值严格大于 $lim$ 的边数不超过 $K$ 个**。
  由于阈值 $lim$ 的取值具有明显的单调性，对 $lim$ 进行二分。
  * **$\text{check}(lim)$ 实现**：
    我们将原图中所有边权 $> lim$ 的边权临时视作 $1$，边权 $\le lim$ 的边权视为 $0$。
    那么，整个问题转化成了：**在新图上求从 $1$ 到 $N$ 的最短路，判断最短路径总长度是否 $\le K$**。
    由于新图边权只有 0 和 1，我们可以直接使用**双端队列 BFS（Deque BFS / 0-1 BFS）**进行 $O(V + E)$ 最优时间复杂度的求解。

```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1005;
struct Edge { int v, w; };
vector<Edge> g[N];
int n, p, k;
int d[N];

bool check(int lim) {
    for (int i = 1; i <= n; ++i) d[i] = 1e9;
    deque<int> q;
    d[1] = 0;
    q.push_front(1);

while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (auto e : g[u]) {
            int v = e.v;
            int cost = e.w > lim; // 边权大于 lim 算 1，否则算 0
            if (d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                if (cost == 1) q.push_back(v); // 1-cost 挂在队尾
                else q.push_front(v);          // 0-cost 挂在队首
            }
        }
    }
    return d[n] <= k;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> p >> k)) return 0;
    
    int max_w = 0;
    for (int i = 0; i < p; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w}); g[v].push_back({u, w});
        max_w = max(max_w, w);
    }

int l = 0, r = max_w, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试继续减小收费上限
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}
```

---

## 7. 三分搜索（Ternary Search）

### 7.1 单峰与单谷函数极值原理
如果函数在一个闭区间 $[L, R]$ 内具有**单峰（极高值）**或**单谷（极低值）**属性（非单调函数，形如抛物线），我们无法直接利用常规二分法。此时需要采用**三分搜索**。

三分法在当前探测区间 $[l, r]$ 内，均匀取两个划分点 $m\_1$ 和 $m\_2$：
$$m\_1 = l + \frac{r - l}{3}$$
$$m\_2 = r - \frac{r - l}{3}$$

#### 舍弃区间决策逻辑：
* **求极低值（单谷函数）**：
  * 若 $f(m\_1) < f(m\_2)$：说明极低点谷底一定不可能在右侧三等分区间 $[m\_2, r]$ 之外。我们将右边界缩减：`r = m2`。
  * 若 $f(m\_1) \ge f(m\_2)$：说明极低点不可能在左侧三等分区间 $[l, m\_1]$。我们将左边界增进：`l = m1`。
* 区间范围每次都缩减到原长度的 $\frac{2}{3}$，时间复杂度为 $O(\log\_{1.5} \text{Range})$。

```
          Valley Bottom
             │
             ▼
        \          /
         \  m1    / m2
          \  *   /   *
           \  \ /   /
            \  v   /
             \____/
  [  l  ] ──> [  r  ]
```

---

### 7.2 三分通用模板

#### 7.2.1 实数域三分模板
```cpp
double ternary_search_double(double L, double R) {
    double l = L, r = R;
    for (int i = 0; i < 100; ++i) { // 稳健迭代 100 次
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (eval(m1) < eval(m2)) {
            r = m2; // 寻找极低值（谷），排除右 1/3
        } else {
            l = m1; // 排除左 1/3
        }
    }
    return eval(l);
}
```

#### 7.2.2 整数域三分模板
在整数域三分中，由于离散取整会阻碍区间收缩，为了规避死循环，我们应当**在区间缩小到一定范围时（如 $r - l < 3$），直接对剩余微小区间执行暴力迭代搜索**。
```cpp
long long ternary_search_int(long long L, long long R) {
    long long l = L, r = R;
    while (r - l >= 3) {
        long long m1 = l + (r - l) / 3;
        long long m2 = r - (r - l) / 3;
        if (eval(m1) < eval(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    long long ans = eval(l); // 对最终缩小的极小物理区间做暴力搜索
    for (long long i = l + 1; i <= r; ++i) {
        ans = min(ans, eval(i));
    }
    return ans;
}
```

---

### 7.3 经典例题：CF1355E - Restorer Distance
* **题意**：
  有 $N$ 根柱子，第 $i$ 根的高度为 $h\_i$。
  我们可以选择执行如下三种操作：
  1. 增高一根柱子 1 物理高度，成本为 $A$。
  2. 削矮一根柱子 1 物理高度，成本为 $R$。
  3. 将一根柱子的高度直接削减 1 并将多余泥土增补到另一根矮柱子上，成本为 $M$。
  求将所有柱子调整到相同目标高度 $H$ 的**最低成本**。

* **分析**：
  最终总调整成本函数 $TC(H)$ 是关于目标高度 $H$ 的一个单谷（凸）函数，适合对高度进行**整数域三分搜索**。

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
int n;
long long a, r, m;
long long h[N];

// 评估函数：将所有柱子高度整体统一更改为 H 高时的最低总开销
long long eval(long long H) {
    long long add = 0, rem = 0;
    for (int i = 0; i < n; ++i) {
        if (h[i] < H) add += H - h[i];
        else rem += h[i] - H;
    }
    long long ans = add * a + rem * r;
    long long mov = min(add, rem);
    // 关键替代：看先削再加、与直接整体转运，哪个花费更小
    ans = min(ans, mov * m + (add - mov) * a + (rem - mov) * r);
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> a >> r >> m)) return 0;
    m = min(m, a + r); // 安全代换：转运开销不应超过拆削加筑之和
    for (int i = 0; i < n; ++i) cin >> h[i];

long long l = 0, r_boundary = 1e9;
    while (r_boundary - l >= 3) {
        long long m1 = l + (r_boundary - l) / 3;
        long long m2 = r_boundary - (r_boundary - l) / 3;
        if (eval(m1) < eval(m2)) r_boundary = m2;
        else l = m1;
    }

long long ans = -1;
    for (long long i = l; i <= r_boundary; ++i) {
        long long cur = eval(i);
        if (ans == -1 || cur < ans) ans = cur;
    }
    cout << ans << "\n";
    return 0;
}
```

---

## 8. 调试技巧与全策略总结

1. **隔离并检验核心判定子函数（$\text{check}$ / $\text{eval}$）**：在遇到二分失败时，首先在入口前用几组手算边界条件直接执行一下 `check` 函数本身，看看判断逻辑是否正确，此为最频繁的出错点。
2. **警惕边界越界**：在构建二分区间 $[l, r]$ 时，初始范围是否安全覆盖了所有合理解空间？有些题目的 $r$ 设为答案上界，而极端数据可能导致无解，哨兵值（无解标示）设计是否正确极为重要。
3. **输出中间调试追踪**：
   ```cpp
   // 在二分循环中打印
   // cout << "l = " << l << ", r = " << r << ", mid = " << mid << endl;
   ```
   这能极其敏锐地发现是否陷入死循环、以及在 check 结果偏向时范围收缩是否正常。

二分与三分算法（Binary & Ternary Search）

1. 二分查找的思想本质

1.1 猜数游戏的直觉

假设我们玩一个猜数游戏：我心里想一个 $1$ 到 $1000$ 之间的整数，你来猜。每次我只会告诉你“猜小了”或“猜大了”。 * 线性查找：若从 $1$ 开始挨个猜，最坏情况下要猜 $1000$ 次。 * 对半折半：若你第一次猜 $500$，若我说“小了”，范围缩至 $[501, 1000]$；若说“大了”，范围缩至 $[1, 499]$。无论结果如何，你都排除了一半的可能性。持续折半，最多只需 $\log_2 1000 \approx 10$ 次猜数即可锁定答案。

这就是二分的直觉来源：通过判断中点状态，每次可靠地排除半数搜索空间，以对数时间复杂度极速逼近目标。

1.2 核心基石：单调性与判定条件

二分查找并非只能用在“排好序的数组里找数”。二分能生效的本质，是判定条件的单调性（Monotonicity）。

设判定函数为 $\text{check}(x)$。若存在一个临界点 $ans$，使得当 $x$ 在 $ans$ 左侧时 $\text{check}(x)$ 恒为假（False），在右侧时恒为真（True），则 $\text{check}(x)$ 对 $x$ 具有单调性。这意味着真假值序列呈现 $\text{F, F, \dots, F, T, T, \dots, T}$ 或 $\text{T, T, \dots, T, F, F, \dots, F}$ 的形态。二分的目标就是精确定位 F 与 T 的分界点。 * 例 1：在升序数组 $a$ 中寻找首个不小于 $v$ 的元素。判定条件为 $a[i] \ge v$，具有单调性。 * 例 2：求解方程 $f(x) = C$（$f(x)$ 递增）。判定条件 $\text{check}(x)$ 设为 $f(x) \ge C$，同样具有单调性。

1.3 搜索空间 $[l, r]$ 的精确界定

闭区间 $[l, r]$：表示 $l$、$r$ 及其之间所有的值均为潜在候选解。整数二分最常采用此定义。
半开区间 $[l, r)$：表示候选解范围在 $l$ 到 $r-1$ 之间，$r$ 本身不含。
初始状态下，$l$ 和 $r$ 的边界必须完全覆盖所有可能的合法解，若设定的边界范围太窄，会直接遗漏真解。

2. 整数域上的二分搜索

整数二分的核心在于：中点 mid 的计算、左右边界的更新策略以及循环终止条件，这三者必须协同一致，否则极易陷入越界或死循环。

2.1 记录答案型模板（推荐，闭区间 $[l, r]$ 且维护 `ans`）

该模板结构清晰，多设置一个 ans 变量记录合法候选解，可以有效避免边界退化造成的死循环，极其推荐初学者与竞赛选手作为首选。

模式 (1)：查找第一个使 $\text{check}(x)$ 为真的 $x$ (首个 $\text{T}$ 点)

真假值序列分布为：$\text{F, F, \dots, F, [T], T, \dots, T}$

// 目标：寻找最小的 x (L <= x <= R)，使得 check(x) 为真
long long find_first_true(long long L, long long R) {
    long long l = L, r = R;
    long long ans = R + 1; // 哨兵值：初始化为上界外，代表可能无解
    while (l <= r) {
        long long mid = l + (r - l) / 2; // 防溢出的向下取整计算
        if (check(mid)) {
            ans = mid;    // mid 是当前合法候选解，记录
            r = mid - 1;  // 尝试在左半区间 [l, mid - 1] 寻找更小的解
        } else {
            l = mid + 1;  // mid 不满足条件，解必在右半区间 [mid + 1, r]
        }
    }
    return ans;
}

模式 (2)：查找最后一个使 $\text{check}(x)$ 为真的 $x$ (最后一个 $\text{T}$ 点)

真假值序列分布为：$\text{T, T, \dots, [T], F, F, \dots, F}$

// 目标：寻找最大的 x (L <= x <= R)，使得 check(x) 为真
long long find_last_true(long long L, long long R) {
    long long l = L, r = R;
    long long ans = L - 1; // 哨兵值：初始化为下界外
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;    // mid 是合法候选解，记录
            l = mid + 1;  // 尝试在右半区间 [mid + 1, r] 寻找更大的解
        } else {
            r = mid - 1;  // mid 不满足条件，解必在左半区间 [l, mid - 1]
        }
    }
    return ans;
}

2.2 收敛型模板（边界直接收缩）

该模板不依赖额外的记录变量 ans，而是通过区间 $[l, r]$ 的不断收缩判定，最终使 $l$ 与 $r$ 重合即为答案。

模式 (1)：查找第一个使 $\text{check}(x)$ 为真的 $x$ (区间收敛到首个 $\text{T}$ 点)

// 目标：在 [L, R] 内寻找满足条件的最小 x
long long find_first_true_收敛(long long L, long long R) {
    long long l = L, r = R + 1; // 搜索区间设计为左闭右开 [l, r)
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;     // mid 可能是解，答案在 [l, mid]
        } else {
            l = mid + 1; // mid 不是解，答案在 [mid + 1, r)
        }
    }
    return l; // 最终 l == r 便是所求点，若无解会收敛到 R + 1
}

模式 (2)：查找最后一个使 $\text{check}(x)$ 为真的 $x$ (区间收敛到最后一个 $\text{T}$ 点)

// 目标：在 [L, R] 内寻找满足条件的最大 x
long long find_last_true_收敛(long long L, long long R) {
    long long l = L, r = R;
    while (l < r) {
        // 特别注意：此处 mid 必须向上取整，否则当 r = l + 1 且 check(l) 成立时
        // mid 算出来依然等于 l，执行 l = mid 会导致 l 无法移动，陷入死循环
        long long mid = l + (r - l + 1) / 2; 
        if (check(mid)) {
            l = mid;     // mid 可能是解，区间缩为 [mid, r]
        } else {
            r = mid - 1; // mid 不是解，区间缩为 [l, mid - 1]
        }
    }
    return l; // 最终重合，可能为解，需在外部进行二次合法性校验
}

2.3 边界条件与避坑指南

防止整型加法溢出：不要写成 mid = (l + r) / 2。当 $l$ 和 $r$ 的和超出整型上限时会导致计算错误，应当写成： $$\text{mid} = l + \frac{r - l}{2}$$
死循环成因：收敛型模板中，若是向左（减小）收缩且采用向下取整时，容易因不位移产生死循环。必须牢记：若在 check 成立时令 l = mid，计算 mid 时必须向上取整 l + (r - l + 1) / 2。

2.4 典型示例：排序数组查找与二分界限（std::lower_bound 模拟）

题意：给定升序数组 $a$ 和目标值 $v$，求 $v$ 的首次出现位置和出现次数。
原理：
首次出现位置：即满足 $a[i] \ge v$ 的首个位置（对应 lower_bound）。
首次大于其的位置：即满足 $a[i] > v$ 的首个位置（对应 upper_bound）。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100005;
int a[N];
int n;

// 模拟 lower_bound: 查找第一个 >= v 的位置
int lb(int v) {
    int l = 0, r = n; // 区间 [0, n)，n 为哨兵代表无解
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= v) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 模拟 upper_bound: 查找第一个 > v 的位置
int ub(int v) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > v) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    n = 7;
    int tmp[] = {2, 5, 5, 5, 8, 10, 12};
    for (int i = 0; i < n; ++i) a[i] = tmp[i];

    int v = 5;
    int first_pos = lb(v);
    int upper_pos = ub(v);

    if (first_pos < n && a[first_pos] == v) {
        cout << "首次出现位置: " << first_pos << "\n";
        cout << "总出现次数: " << upper_pos - first_pos << "\n";
    } else {
        cout << "元素不存在\n";
    }
    return 0;
}

2.5 经典例题：CF1352C - K-th Not Divisible by n

题意：给定 $n$ 和 $k$，求出第 $k$ 个不能被 $n$ 整除的正整数。
分析：设 $f(x)$ 为区间 $[1, x]$ 内不能被 $n$ 整除的数的个数： $$f(x) = x - \lfloor \frac{x}{n} \rfloor$$ 因为 $f(x)$ 随着 $x$ 增加具有明显的单调递增性。我们要寻找最小的 $x$ 使满足： $$f(x) \ge k$$ 这完美对应了“寻找第一个使检测条件为真的 $x$”模型。

#include <iostream>
using namespace std;

long long n, k;

// 判定函数：前 v 个数内，不能被 n 整除的数是否达到了 k 个
bool check(long long v) { 
    return v - v / n >= k; 
}

void solve() {
    cin >> n >> k;
    long long l = 1, r = 2e9 + 7; // 设置一个安全且足够大的右界
    long long ans = r;
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试向左逼近更小的值
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}

3. 实数域（浮点数）二分搜索

实数二分无偏位对齐和边界退化取整问题。当答案在实数域内连续分布时，我们仅需要找到在满足特定精度误差 eps 约束下的近似解。

3.1 核心机制

精度控制手段：
循环判定控制精度：while (r - l > eps)。使用该手段必须极度小心精度限制，若 eps 选得过小，由于浮点精度表示存在缺陷会导致陷入死循环。
固定循环迭代次数：最稳健、最推荐的做法。直接强制迭代 100 次。因为经过 $100$ 次折半拆分，搜索范围会被缩减到原始空间的 $2^{-100} \approx 10^{-30}$，可以绝对覆盖绝大多数竞赛题目的精度要求，甚至在部分由于运算可能产生负相关的极端用例下也绝不会产生死循环。

3.2 实数二分模板（固定迭代 100 次）

// 寻找最小的 x 使得 check(x) 成立
double float_binary_search(double L, double R) {
    double l = L, r = R;
    for (int i = 0; i < 100; ++i) { // 强力循环迭代 100 次
        double mid = l + (r - l) / 2.0;
        if (check(mid)) {
            r = mid; // 答案在 [l, mid]
        } else {
            l = mid; // 答案在 [mid, r]
        }
    }
    // 当迭代完毕，l 和 r 极度逼近。寻找最小真值点，上界 r 比下界 l 更稳健
    return r;
}

3.3 典型示例：求解方程 $x^P = V$（求实数开根）

题意：给定非负实数 $V$ 与正实数 $P$，求解 $x$ 使得 $x^P = V$。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

double v, p;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(10);

    v = 27.0; p = 3.0; // 计算 27.0 的三次方根
    double l = 0.0, r = max(1.0, v); // 初始化安全右边界

    for (int i = 0; i < 100; ++i) {
        double mid = l + (r - l) / 2.0;
        if (pow(mid, p) >= v) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << "\n"; // 输出: 3.0000000000
    return 0;
}

4. 二分答案（Binary Search on Answers）

答案二分是将“求一个最优值”这一极具策略和动态变数的最优化问题，巧妙逆向映射、降维为一连串只需判定“可行或不可行”的判定性问题的技巧。

4.1 核心思想

若所求的最终最优答案满足单调性： * 求最小值的最大化（对应 $\text{T, T, \dots, T, F, F, \dots, F}$）：寻找最右侧合法点。 * 求最大值的最小化（对应 $\text{F, F, \dots, F, T, T, \dots, T}$）：寻找最左侧合法点。我们就可以直接对“答案的值”建立二分空间 $[l, r]$，每次猜测一个值 $mid$，并通过 $\text{check}(mid)$ 检验该答案在物理条件上是否存在解。

4.2 典型例题一：CF165B - Burning Midnight Oil

题意：写一本书共 $n$ 行代码。首轮写 $v$ 行，下一轮衰减为 $\lfloor v / k \rfloor$，再下一轮 $\lfloor v / k^2 \rfloor$，直至变为 $0$。求能完成任务的最小初始值 $v$。
分析：初始值 $v$ 越低，能写的代码总行数 $S$ 越少。存在单调性：若某个 $v$ 成立，则所有 $> v$ 的值必然也成立。目标是寻找满足条件的最小 $v$，属于“最大值的最小化”（寻找首个 $T$）。

#include <iostream>
using namespace std;

long long n, k;

// check 函数：初始写 v 行，代码总量是否能满足 n 行
bool check(long long v) {
    long long sum = 0, cur = v;
    while (cur > 0) {
        sum += cur;
        if (sum >= n) return true;
        cur /= k;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> k)) return 0;

    long long l = 1, r = n, ans = n;
    while (l <= r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试在左半段探测是否有更小的值
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

4.3 典型例题二：CF812C - Sagheer and Nubian Market

题意：有 $n$ 件商品，第 $i$ 件的基础价格为 $a_i$。如果总共购买 $k$ 件物品，则第 $i$ 件商品的价格变更为 $a_i + i \times k$。当前预算为 $S$。求在预算充裕的前提下最多能买多少件商品，以及此时对应的最小总开销。
分析：可购买商品数 $k$ 具有完美的单调性。若能买 $k$ 件，则购买 $k-1$ 件必然可实现。目标是最大化 $k$（寻找最后一个 $T$）。
$\text{check}(k)$ 的实现：当确定购买数 $k$ 时，我们直接计算各商品对应的价格 $b[i] = a[i] + i \times k$，对其进行排序并选择最便宜的前 $k$ 个，检验其和是否在预算 $S$ 之内即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
int n;
long long s;
long long a[N];
long long b[N]; // 临时价格计算存储器

pair<bool, long long> check(int k) {
    if (k == 0) return {true, 0};
    for (int i = 0; i < n; ++i) {
        b[i] = a[i] + (long long)(i + 1) * k; // 商品下标 1-indexed
    }
    sort(b, b + n); // 贪心选取最便宜的
    long long sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += b[i];
    }
    return {sum <= s, sum};
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> s)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int l = 0, r = n;
    int ans_k = 0;
    long long ans_cost = 0;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (mid == 0) {
            l = mid + 1; continue;
        }
        auto res = check(mid);
        if (res.first) {
            ans_k = mid;
            ans_cost = res.second;
            l = mid + 1; // 尝试去买更多件
        } else {
            r = mid - 1;
        }
    }
    cout << ans_k << " " << ans_cost << "\n";
    return 0;
}

5. 进阶：二分答案与 0-1 分数规划（Fractional Programming）

0-1 分数规划是指用于优化形如“多项式比率”一类的特殊极值问题： $$\text{Maximize/Minimize} \quad R(x) = \frac{\sum_{i=1}^n a_i \cdot x_i}{\sum_{i=1}^n b_i \cdot x_i} \quad (x_i \in {0, 1})$$

5.1 判定问题转换推导

由于比率极其不便在状态转移时直接累加，我们采用答案二分。以最大化比率为例，猜测一个比率 $ans$。若存在一种可行解方案使其比率不低于 $ans$，则有： $$\frac{\sum a_i x_i}{\sum b_i x_i} \ge ans$$

假定分母大于零（通常代表总重量/总量在实际场景中非空），通过去分母变形： $$\sum a_i x_i \ge ans \cdot \sum b_i x_i \implies \sum (a_i - ans \cdot b_i) \cdot x_i \ge 0$$

令元素的新价值（权值）为： $$d_i = a_i - ans \cdot b_i$$ 问题转化为：是否存在一种选择方案，满足特定约束的前提下，使选择的新权值和非负：$\sum d_i x_i \ge 0$。

5.2 经典例题：洛谷 P4377 [USACO18OPEN] Talent Show G

题意：有 $N$ 头牛，第 $i$ 头重量为 $w_i$，才艺值为 $t_i$。我们需要从中挑选若干头牛组成战队。要求所挑牛的总重量不少于 $W$。目标是最大化：(总才艺值) / (总重量)。
题解核心：二分最终比率 $ans$。构造新价值 $d[i] = t[i] - ans \times w[i]$。问题转化为：在挑出的牛“总重量至少为 $W$”的前提下，最大化新价值的总和 $\sum d[i]$ 是否大于或等于 0。这是一个经典的0-1 背包最优化问题。
DP 状态设计： dp[j] 表示当前选取牛的“总重量至少为 $j$”时的最大价值。 $$dp[\min(W, j + w_i)] = \max(dp[\min(W, j + w_i)], dp[j] + d_i)$$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 255, W_MAX = 1005;
int n, w0;
int w[N], t[N];
double d[N];
double dp[W_MAX];

bool check(double ans) {
    for (int i = 1; i <= n; ++i) {
        d[i] = (double)t[i] - ans * w[i];
    }
    for (int i = 1; i <= w0; ++i) dp[i] = -1e18; // 初始化为极小值
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = w0; j >= 0; --j) {
            int nxt = min(w0, j + w[i]); // 超过总量限制均归并至 w0 处
            dp[nxt] = max(dp[nxt], dp[j] + d[i]);
        }
    }
    return dp[w0] >= 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> w0)) return 0;
    for (int i = 1; i <= n; ++i) cin >> w[i] >> t[i];

    double l = 0, r = 1005.0; // 极值上界估算
    for (int i = 0; i < 100; ++i) {
        double mid = l + (r - l) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << (long long)(l * 1000) << "\n"; // 按题意乘以 1000 并向下取整
    return 0;
}

6. 进阶：二分与图论结合

6.1 二分 + 0-1 BFS 最短路问题

当判定条件需要验证连通性，或需要解一条带有权值瓶颈的特定路径时，我们将二分答案与图论算法深度结合。

6.2 经典例题：洛谷 P1948 [USACO08JAN] Telephone Lines S

题意：一个无向带权图，包含 $N$ 个节点、$P$ 条边。现在可以任意指定 $K$ 条边免费（权值清 0）。求在挑选出的所有连接 $1$ 到 $N$ 的路径中，剩下的最贵收费边的最小可能值是多少。
分析：我们需要寻找一个最小的收费阈值 $lim$，使得存在一条从 $1$ 到 $N$ 的路径，其中权值严格大于 $lim$ 的边数不超过 $K$ 个。由于阈值 $lim$ 的取值具有明显的单调性，对 $lim$ 进行二分。
$\text{check}(lim)$ 实现：我们将原图中所有边权 $> lim$ 的边权临时视作 $1$，边权 $\le lim$ 的边权视为 $0$。那么，整个问题转化成了：在新图上求从 $1$ 到 $N$ 的最短路，判断最短路径总长度是否 $\le K$。由于新图边权只有 0 和 1，我们可以直接使用双端队列 BFS（Deque BFS / 0-1 BFS）进行 $O(V + E)$ 最优时间复杂度的求解。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1005;
struct Edge { int v, w; };
vector<Edge> g[N];
int n, p, k;
int d[N];

bool check(int lim) {
    for (int i = 1; i <= n; ++i) d[i] = 1e9;
    deque<int> q;
    d[1] = 0;
    q.push_front(1);

    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (auto e : g[u]) {
            int v = e.v;
            int cost = e.w > lim; // 边权大于 lim 算 1，否则算 0
            if (d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                if (cost == 1) q.push_back(v); // 1-cost 挂在队尾
                else q.push_front(v);          // 0-cost 挂在队首
            }
        }
    }
    return d[n] <= k;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> p >> k)) return 0;

    int max_w = 0;
    for (int i = 0; i < p; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w}); g[v].push_back({u, w});
        max_w = max(max_w, w);
    }

    int l = 0, r = max_w, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1; // 尝试继续减小收费上限
        } else {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

7. 三分搜索（Ternary Search）

7.1 单峰与单谷函数极值原理

如果函数在一个闭区间 $[L, R]$ 内具有单峰（极高值）或单谷（极低值）属性（非单调函数，形如抛物线），我们无法直接利用常规二分法。此时需要采用三分搜索。

三分法在当前探测区间 $[l, r]$ 内，均匀取两个划分点 $m_1$ 和 $m_2$： $$m_1 = l + \frac{r - l}{3}$$ $$m_2 = r - \frac{r - l}{3}$$

舍弃区间决策逻辑：

求极低值（单谷函数）：
若 $f(m_1) < f(m_2)$：说明极低点谷底一定不可能在右侧三等分区间 $[m_2, r]$ 之外。我们将右边界缩减：r = m2。
若 $f(m_1) \ge f(m_2)$：说明极低点不可能在左侧三等分区间 $[l, m_1]$。我们将左边界增进：l = m1。
区间范围每次都缩减到原长度的 $\frac{2}{3}$，时间复杂度为 $O(\log_{1.5} \text{Range})$。

          Valley Bottom
             │
             ▼
        \          /
         \  m1    / m2
          \  *   /   *
           \  \ /   /
            \  v   /
             \____/
  [  l  ] ──> [  r  ]

7.2 三分通用模板

7.2.1 实数域三分模板

double ternary_search_double(double L, double R) {
    double l = L, r = R;
    for (int i = 0; i < 100; ++i) { // 稳健迭代 100 次
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (eval(m1) < eval(m2)) {
            r = m2; // 寻找极低值（谷），排除右 1/3
        } else {
            l = m1; // 排除左 1/3
        }
    }
    return eval(l);
}

7.2.2 整数域三分模板

在整数域三分中，由于离散取整会阻碍区间收缩，为了规避死循环，我们应当在区间缩小到一定范围时（如 $r - l < 3$），直接对剩余微小区间执行暴力迭代搜索。

long long ternary_search_int(long long L, long long R) {
    long long l = L, r = R;
    while (r - l >= 3) {
        long long m1 = l + (r - l) / 3;
        long long m2 = r - (r - l) / 3;
        if (eval(m1) < eval(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    long long ans = eval(l); // 对最终缩小的极小物理区间做暴力搜索
    for (long long i = l + 1; i <= r; ++i) {
        ans = min(ans, eval(i));
    }
    return ans;
}

7.3 经典例题：CF1355E - Restorer Distance

题意：有 $N$ 根柱子，第 $i$ 根的高度为 $h_i$。我们可以选择执行如下三种操作：
增高一根柱子 1 物理高度，成本为 $A$。
削矮一根柱子 1 物理高度，成本为 $R$。
将一根柱子的高度直接削减 1 并将多余泥土增补到另一根矮柱子上，成本为 $M$。求将所有柱子调整到相同目标高度 $H$ 的最低成本。
分析：最终总调整成本函数 $TC(H)$ 是关于目标高度 $H$ 的一个单谷（凸）函数，适合对高度进行整数域三分搜索。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
int n;
long long a, r, m;
long long h[N];

// 评估函数：将所有柱子高度整体统一更改为 H 高时的最低总开销
long long eval(long long H) {
    long long add = 0, rem = 0;
    for (int i = 0; i < n; ++i) {
        if (h[i] < H) add += H - h[i];
        else rem += h[i] - H;
    }
    long long ans = add * a + rem * r;
    long long mov = min(add, rem);
    // 关键替代：看先削再加、与直接整体转运，哪个花费更小
    ans = min(ans, mov * m + (add - mov) * a + (rem - mov) * r);
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (!(cin >> n >> a >> r >> m)) return 0;
    m = min(m, a + r); // 安全代换：转运开销不应超过拆削加筑之和
    for (int i = 0; i < n; ++i) cin >> h[i];

    long long l = 0, r_boundary = 1e9;
    while (r_boundary - l >= 3) {
        long long m1 = l + (r_boundary - l) / 3;
        long long m2 = r_boundary - (r_boundary - l) / 3;
        if (eval(m1) < eval(m2)) r_boundary = m2;
        else l = m1;
    }

    long long ans = -1;
    for (long long i = l; i <= r_boundary; ++i) {
        long long cur = eval(i);
        if (ans == -1 || cur < ans) ans = cur;
    }
    cout << ans << "\n";
    return 0;
}

8. 调试技巧与全策略总结

隔离并检验核心判定子函数（$\text{check}$ / $\text{eval}$）：在遇到二分失败时，首先在入口前用几组手算边界条件直接执行一下 check 函数本身，看看判断逻辑是否正确，此为最频繁的出错点。
警惕边界越界：在构建二分区间 $[l, r]$ 时，初始范围是否安全覆盖了所有合理解空间？有些题目的 $r$ 设为答案上界，而极端数据可能导致无解，哨兵值（无解标示）设计是否正确极为重要。
输出中间调试追踪： cpp // 在二分循环中打印 // cout << "l = " << l << ", r = " << r << ", mid = " << mid << endl; 这能极其敏锐地发现是否陷入死循环、以及在 check 结果偏向时范围收缩是否正常。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com