二分的大一统的初步尝试
xuanyu722
·
·
算法·理论
前言
众所周知，二分查找/答案的代码是最容易写错的代码之一。
为啥？
因为：模板，没背。贪心，不会。证明，没懂。思路，没有。
所以：写毛啊。
所以：你来对的地方了。这篇题解，将结合个人经验与理解，以及东拼西凑的能力，阐述二分的基本原理与框架。
二分逻辑分类
先不考虑二分答案的贪心逻辑。
二分，分别在单调性，最终答案的选择，自变量与因变量的数集上的三个不同属性的组合下，能组合出逻辑完全不同的几个逻辑。
通常有以下具体情况：
- 单调性：单调递增，单调递减。
（注：都是非严格意义下的）。
- 最终答案的选择：第一个满足条件，第一个不满足条件，最后一个满足条件。
- 数集对应关系：整数集映射到整数集，实数集映射到实数集，实数集映射到整数集。
（注：整数集映射到实数集，在实际意义下，行为与整数集映射到整数集类似）。
综上，一共 2 \times 3 \times 3 = 18 种情况。
不过在揭示具体框架前，先让我们来重新认识二分查找。
统一的思路
三个疑问
我们最先接触到的二分逻辑应该是，对于一个单调递增函数 f(x)，x \in \{x \in \mathbb{Z} \mid 0 \le x < n\}。
要查找第一个等于 val 的位置。
初始时，取最大有效的左闭右开查找区间 [l, r)，之后对于每次循环，mid \gets \lfloor (l + r) / 2 \rfloor。
如果 f(mid) \ge val，则 r \gets mid；否则，l \gets mid + 1。
但是，这段对于二分查找的算法描述几乎没有直观地揭示任何有关二分的信息。
比方说：
- 为什么一定能够最后查找到第一个满足条件的值？
- 为什么一定要取左闭右开区间？
- 为什么这个二分查找一定不会进入死循环？
不过我们先暂时不解决这些问题，让我观察一个更简单的场景。
Left
假设我们有一个很长的整数数列 a，下标在 [0, n - 1]，我们被提前告知了：
- 这个数列是单调递增的。
- 这个数列上存在一个数等于 val。
问：我们要找 val 第一次出现的位置。
那么你会怎么做？
首先，最容易想到的两个解法：
顺序遍历，直到第一次找到我们想要的值，然后退出循环输出这个值的下标；
逆序遍历，直到我们第一次找到小于 val 的值，输出上一次遍历得到值的下标。
但是，别忘了，这个数列很长同时具有单调性。
这意味着，我们的顺序遍历可能会经历很长的小于 val 的阶段。
反过来，如果逆序遍历，我们可能会经历很长一段大于或等于 val 的阶段。
那么自然就可以想到原数列具有“二段性”。
进而我们可以对原数列每个元素求 a _ {i} \ge val；得到一个布尔数列 [F, F, \dots, F, T, \dots, T]，记作 b。
同时我们把第一个使得条件成立的下标记作 ans。
容易观察得到，第一个满足 a _ {i} \ge val 的元素，即是我们想要的元素。
那么这个元素的位置具有什么其它位置没有的特殊的性质？
我们容易发现，它自身及其右边都满足 a _ {i} \ge val，这个元素的左边都不满足 a _ {i} \ge val，即满足 a _ {i} < val。
那么，我们是否可以使用两个表示位置的变量来分别记录这两个属性呢？
然后，我们是不是可以认为这两个位置重合的时候就是我们想要找的位置呢？
答案是肯定的。
我们就可以定义：
$r$：**它自身的元素及其右边**都是**满足** $a _ {i} \ge val$ 的**位置**。
**如果 $l$ 和 $r$ 重合：$l = r$，那么就说明 $l$ 或 $r$ 就是我们要找的元素的位置。**
接下来，问题就变得简单了：
我们先把 $l$ 确定为数列的最左端（`l = 0`），再把 $r$ 确定为最右端右边一个不存在的元素（`r = n`）。
如果能通过不断迭代，使得 $l$ 和 $r$ 在其各自含义不变下，逐渐靠近。
那么，最后它们重合的位置，就是我们的答案。
---
### Mid
**但是应该怎么靠近？**
题目的单调递增性，给我们提供了一个捷径：
**对于数列 $a$ 中任意一个元素，如果我们知道这个元素大于等于 $val$，那么它及其右边的值都大于等于 $val$：**
$$a _ {i} \ge val \implies \forall j \ge i, a _ {j} \ge val$$
**反之：**
$$a _ {i} < val \implies \forall j < i, a _ {j} < val$$
由此，如果我们在 $[l, r)$ 内随机取一个下标 $k$，如果这个值满足 $a _ {k} \ge val$，那么能够确定它右边的数都满足这个条件，且它的位置可能是 $ans$，而它右边的一定不是。我们便可以顺理成章地**把 $r$ 赋值为 $k$**。
反之，如果这个值满足 $a _ {k} < val$，那么我们一定能够确定它左边的数都不满足这个条件，且它自身也一定不是 $ans$。我们便可以顺理成章地**把 $l$ 赋值为 $k + 1$**。
**以上，就确定了二分的定性内容。**
**以下，开始定量分析。**
我们可以想到，随机取的 $k$ 值，不仅效率不稳定，同时有可能陷入死循环。
**那么怎么取这个 $k$ 的值，才合理？**
首先考虑这样一个情况，如果满足各自定义的 $l$ 和 $r$ 在循环前就**相邻**怎么办？
根据定义，$l$ 此时的位置是**未经条件判断过的**，而 $r$ 的位置**已经满足了条件**，有可能作为最终的答案。
那么我们只需要判断一次 $l$ 的位置的值，再决定 $l$ 更新，还是 $r$ 更新即可。
最终都会导致 $l$ 和 $r$ 的重合发生，从而确定答案。
即，此时 **$k$ 的取值逻辑就一定需要满足在 $l$ 和 $r$ 相相邻时，优先落在 $l$ 上判断。**
同时，我们反过来想，如果 $l$ 和 $r$ 在循环的最后无论如何都不能相邻，那么它们一定不能重合。
所以 **$k$ 的取值逻辑一定要满足在 $l$ 和 $r$ 不相邻时，通过不断迭代最后使得它们相邻。**
---
### Right
对于一般情况，我们便可以总结出以下三点要求：
1. $l$ 和 $r$ 相邻时，$k$ 优先取 $l$ 进行判断；
2. $l$ 和 $r$ 不相邻时，$k$ 的取值逻辑能通过不断迭代使得 $l$ 和 $r$ 相邻；
3. $k$ 取的次数越少越好。
**进行推导：**
* $l$ 和 $r$ 重合 $\iff r - l = 0$。
* $l$ 和 $r$ 相邻 $\iff r - l = 1$。
* $l$ 和 $r$ 不相邻 $\iff r - l > 1$。
那么问题就转换为了：找到一种方法，使得对于任意大于 $1$ 的 $r - l$，在 $k$ 不断迭代的过程中，区间长度 $r - l$ 一定严格递减，并依次经过 $1$ 与 $0$。
同时，我们只能通过判断 $k$ 对应的元素是否满足 $a _ {k} \ge val$ 来筛选元素。
那么 $k$ 在判断后就天然地把 $[l, r)$ 分成两部分（此时 $k$ 的含义要么是 $r$ 要么是 $l$）。
有且只有 $k$ 取 $l$ 和 $r$ 的中点时，这两部分才是最均匀的，从而效率最稳定的。
这决定了该查找算法的最优时间复杂度为 $\mathcal{O}(\log n)$。
注意到，二进制的右移一位操作（即除以 $2$ 向下取整），完美满足了上述所有严苛的数学条件，即：
$$k = \left\lfloor \frac{l + r}{2} \right\rfloor$$
**推导完毕。**
至此我们便 ~~可以在不会查字典的情况下，推导出二分查找~~ 彻底地解答了一开始的三个疑惑 (｀・ω・´)。
在开始下一个节前，读者可以根据以上推导，思考以下两个问题：
* 我们如何通过更改$l$ 和 $r$ 的定义与$l$ 与 $r$ 相相邻时 $k$ 优先取值的逻辑**来得到 $l$ 在循环结束后指向“最后一个满足条件的答案”？
* 为什么 $k$ 一定是除 $2$ 取整，而不是除 $3$ 或者除 $114514$ 取整？明明运行速度更快啊？
---
## What's the point?
我想表达的是，对于这个二分查找，以下代码的**任何一个逻辑都是不能轻易改变**的：
```cpp
int l = 0; int r = n;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= val) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << '\n'; // l 就是 ans
```
那么，我们怎么在改变最少算法逻辑下得到其它的 $17$ 种情况呢？
---
# 统一
## 稍加思考
经过以上的思路，我们可以总结发现：
1. 二分的入手点是第一个满足条件的元素的在“二段性”下的性质。
2. 我们需要考虑在条件作用下从原数组上得到一个什么样的布尔数组。
3. 根据这个数组判断 $r$ 和 $l$ 分别怎么更新。
4. 左闭右开的 $[l, r)$ 区间是要检查的区间，也意味着在 $l$ 和 $r$ 相邻的时候，$l$ 永远是要先检查的部分。
分别翻译成算法语言：
1. 定义 $l$ 和 $r$。
2. 条件在数组的哪些位置满足。
3. 满足条件时，$r$ 怎么更新；不满足时，$l$ 怎么更新。
4. 永远除二向下取整，保证检查区间闭合。
你觉得这四点，哪个最与答案的位置挂钩，最主导算法的逻辑？
**显然是第二点。**
那么我们就可以定义一个 `check` 函数来检查是否满足条件，然后更新 $r$，算法的其它部分完全不变！
即：
$a$ 是原数组。
$val$ 是我们要找的值。
$l$ 仍然是其左边的所有元素都不满足条件；
$r$ 仍然是它及其右边的所有元素都满足条件。
$mid$ 取 $l$ 和 $r$ 中点并向下取整。
根据判断，更新 $r = mid$ 或 $l = mid + 1$。
接下来，请看，一个 `check` 函数是怎么统一整数下不同逻辑的二分算法的。
## 整数的情况
### 单调递增
**找第一个等于 $val$ 的元素：**
即 $r$ 及其右边都大于等于 $val$。
定义 `check` 为 $a _ {mid} \ge val$。
```cpp
while (l < r) {
int mid = (l + r) / 2;
if (v[mid] >= val) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << '\n';
```
**找第一个大于 $val$ 的元素：**
即 $r$ 及其右边都大于 $val$。
定义 `check` 为 $a _ {mid} > val$。
```cpp
while (l < r) {
int mid = (l + r) / 2;
if (v[mid] > val) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l << '\n';
```
**找最后一个等于 $val$ 的元素：**
等价于 $r$ 及其右边都大于 $val$，最后得到的答案下标减 $1$。
定义 `check` 为 $a _ {mid} > val$。
```cpp
while (l < r) {
int mid = (l + r) / 2;
if (v[mid] > val) {
r = mid;
} else {
l = mid + 1;
}
}
cout << l - 1 << '\n';
```
即使是这样，核心代码的逻辑也没有改变，而只需对答案进行一步判断即可。
### 单调递减
以下同理：
**找第一个等于 $val$ 的元素：**
等价于 $r$ 及其右边都小于等于 $val$。
定义 `check` 为 $a _ {mid} \le val$。
**找第一个小于 $val$ 的元素：**
等价于 $r$ 及其右边都小于 $val$。
定义 `check` 为 $a _ {mid} < val$。
**找最后一个等于 $val$ 的元素：**
等价于 $r$ 及其右边都小于 $val$，最后对答案下标减 $1$。
定义 `check` 为 $a _ {mid} < val$。
以 `cout << l - 1 << '\n'` 结束。
---
所以，发现了吗？我们现在可以只问自己一个问题：
在什么条件下，$mid$ 满足 $r$ 的定义？
那么此时我们得到的就是 `check` 函数。
由此便速通了二分，吗？
---
## 实数的情况
### 稍加思考
首先根据初等数学的知识，我们知道 $0$ 和 $0.1$ 之间存在无穷多个数。
那么如果我们仍然依据对整数二分的逻辑，再对实数采取相同的逻辑二分，我们会发现：
没法用向下取整闭合了！
没法定义左闭右开的查找区间了！
连第一个满足条件的数都有可能找不到！
似乎我们有可能折半操作永远进行下去，而可能永远无法精确地找到满足我们定义的数？
答案，确实是这样的。
吗？
现实是现实，计算机是计算机。
不要忘记计算机里的最小刻度以 $2$ 的幂来度量。
具体来说，在计算机里，我们永远无法知道 $\frac{1}{3}$ 里怎么用二进制表示，
但我们却可以在一定精度内表示出离 $\frac{1}{3}$ 最近的二进制数。
既然如此，我们为什么不把这个精度下的二进制数的“单位长度”作为新的整数意义下的“$1$”呢？
那么，我们便可以写出以下代码：
```cpp
const double n = 10.0;
const double eps = 1e-15; // 接近 double 精度极限
double l = 0; double r = n;
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid + eps;
}
}
cout << r << '\n';
```
**至此，统一框架基本已成。**
---
### 问题
不过事实上，
这个实数上的二分和整数上的二分还是有一个区别的，那就是 —— $l$ 和 $r$ 永远无法重合！
由于在循环结束后 $r - l \le eps$，
当且仅当 $eps = 0$ 时，$r$ 和 $l$ 才会重合，但这显然不是永远可能的。
但这个问题，破坏了我们原来的框架吗？
**答案是：没有。**
我们来考虑下这个不重合的具体情况。
比方说，对于一个单调递增函数，我们要找第一个使得 `check(mid)` 等于 $val$ 的数。
问题等价于找第一个使得 `check(mid) >= val` 成立的 $mid$。
假设我们的 $eps = 0$，其它逻辑不变。
那么循环只在一种情况下可以终止：
我们想要找到的 $mid$ 必须是 `double` 精度内表示二进制浮点数。
其它两种情况分别是：
1. $mid$ 能用二进制浮点数表示，但精度不够。
2. $mid$ 不能用二进制浮点数表示。
**所以这告诉我们了什么？**
与其，期望精确地找到一个满足所求的二进制浮点数，而不得不接受不可被表示的数的存在。
我们不如直接在 $l$ 和 $r$ 足够接近的情况下，就认为它们“重合了”，“是一个点”。
由于循环结束后，$r$ 是被判断过满足条件的，而 $l$ 此时没有。
所以我们取 $r$ 作为最后的答案。
即：**在 $r - l$ 达到我们想要的精度的时候，取这个区间的右端点来近似模拟我们想要的值**。
那么，我们就可以对实数二分算法的终点进行总结：
1. 取满足题目条件的精度 $eps$。
2. 二分结束后 $r$ 即是在 $eps$ 下最接近所求的数。
3. 根据实际情况具体讨论答案情况。
注意：$r$ 此时对应的位置不一定是 `check` 第一个等于 $val$ 的位置，
甚至可能小于 $val$。
这么说可能有点抽象，我们接下来用一个具体的题目来讲解。
---
### 一道题目
题目链接：[足球训练](https://www.luogu.com.cn/problem/P16239)
#### 简要思路
假设我们只安排一天，怎么安排，使得实力增长最大？
我们可以把对于任意一名安排一天后，得前后比值为：
$$x = \frac{a _ {i} + (k + 1)b _ {i}}{a _ {i} + k b _ {i}}$$
发现，我们只要在当前挑出这个比值最大的队员进行训练，
对未来的情况来说永远最优，由此确定了我们训练一天的贪心策略。
同时，注意到随着 $k$ 增大，这个式子在不断减小。
那么如果我们可以知道第 $m$ 天分配时这个式子的值是多少，
我们就可以根据单调性倒推出每个队员安排的天数。
**目标：**
找到那个第 $m$ 天对应的这个式子的值。
**式子化简：**
$$x = \frac{a _ {i} + (k + 1)b _ {i}}{a _ {i} + k b _ {i}} = 1 + \frac{b _ {i}}{a _ {i} + k _ {i} b _ {i}}$$
**$k$ 的最大取值：**
$$k _ {i} < \frac{1}{x - 1} - \frac{a _ {i}}{b _ {i}} \implies k _ {i} = \left\lfloor \frac{1}{x - 1} - \frac{a _ {i}}{b _ {i}} \right\rfloor$$
**条件：**
$$\sum _ {i = 1} ^ {n} \left\lfloor \frac{1}{x - 1} - \frac{a _ {i}}{b _ {i}} \right\rfloor \le m$$
**策略：**
二分枚举 $x$，代入条件，如果满足条件，`r = x`；否则，`l = x + eps`。
最后由于精度或不可取点，导致求得的 $r$ 偏大，$m$ 可能未用完，
故开优先队列，存最大的 $x$ 与索引。继续处理未耗尽的天数
**代数运算效率优化：**
$$\max \left( 1 + \frac{b _ {i}}{a _ {i} + k _ {i} b _ {i}} \right) \iff \max \left( \frac{b _ {i}}{a _ {i} + k _ {i} b _ {i}} \right) = \max \left( \frac{1}{\frac{a _ {i}}{b _ {i}} + k _ {i}} \right) \iff \min \left( \frac{a _ {i}}{b _ {i} + k _ {i}} \right)$$
故开最小堆。
**代码如下：**
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <tuple>
#include <cmath>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
using i64 = int64_t;
using per = tuple<double, double, double, int>;
vector<per> meb(n);
for (auto& [a, b, c, k] : meb) {
cin >> a >> b;
c = a / b;
}
auto check = [&] (double x) {
i64 tm = 0;
double tar = 1 / (x - 1);
for (const auto& [a, b, c, k] : meb) {
i64 tk = floor(tar - c);
if (tk > 0) tm += tk;
}
return tm <= m;
};
const double eps = 1e-15;
double l = 1; double r = 1e5 + 2;
while (r - l > eps) {
double x = (l + r) / 2;
if (check(x)) {
r = x;
} else {
l = x + eps;
}
}
double tar = 1 / (r - 1);
int tm = 0;
using node = pair<double, int>;
priority_queue<node, vector<node>, greater<node>> pq;
for (int i = 0; i < n; ++i) {
auto& [a, b, c, k] = meb[i];
k = max(int(floor(tar - c)), 0);
tm += k;
pq.push({c + k, i});
}
while (tm < m && !pq.empty()) {
auto [w, i] = pq.top(); pq.pop();
auto& [a, b, c, k] = meb[i];
++k;
++tm;
pq.push({c + k, i});
}
const int mod = 998244353;
i64 ans = 1;
for (auto [a, b, c, k] : meb) {
ans = ans * (i64(a) + i64(b) * k % mod) % mod;
}
cout << ans << '\n';
return 0;
}
```
**关于精度问题的补充：**
实测 `eps = 1e-9` 效率最高，
也就是说 $m$ 在极端情况的同时，题目所给数据的 $x$ 基本不会小于 $1 + 10 ^ {-9}$。
所以 `eps = 1e-15` 的分辨率是完全足够的。
这里就不给严格的数学推导了。~~（才，才不是作者不会呢）。~~
# 后记
这篇文章花了我不少时间写。~~（刚开始以为几小时就写完了）。~~
写文章的时候出现的问题比我想象中的要多得多。
所以可能会有所疏漏或者不合理的地方。~~（再也不想心血来潮写这种长篇大论了 qwq）。~~
那么，如果你发现了，请在下方留言或者私信我让我知道！
**end。**
ps：本文使用了Gemini进行了检查与润色。