【基础算法】二分 学习笔记

适用范围

两段性：在某个区间内，存在一个分界点，使得分界点一侧满足某性质，另一侧不满足

二分算法适用于具有“两段性”特征的问题，只要有高效的检验性质的方法，就可以在对数复杂度时间内求出分段点的位置。最基础的二分查找有对应 STL 的实现，根据处理数据的不同，还有整数二分和实数二分两种自定义性质检验的实现方式。

代码模板

代码模板-二分

经典例题

二分查找

• 洛谷 P1102 A-B 数对：已知 $N$（$1\le N\le2\times10^5$）个整数 $a_i$（$0\le a_i<2^{30}$）和正整数 $C$（$1\le C<2^{30}$），求满足 $a_i - a_j = C$ 的有序数对 $(i,j)$ 的个数（不同位置算不同）。
• 洛谷 P1678 烦恼的高考志愿：已知学校数 $m$（$1\le m\le 10^5$）、学生数 $n$（$1\le n\le 10^5$），学校分数线数组 $a_i$（$0\le a_i\le 10^6$）和学生估分数组 $b_j$（$0\le b_j\le 10^6$），求 $\sum_{j=1}^{n} \min_{i=1}^{m} |b_j - a_i|$（即每位学生与所有学校分数线的最小绝对差之和）。

整数二分

• 洛谷 P1873 砍树：已知 $N$（$1\le N\le10^6$）棵树的高度 $h_i$（$h_i\le4\times10^5$）和所需木材总长 $M$（$1\le M\le2\times10^9$，且 $\sum h_i > M$），求最大的整数高度 $H$，使得锯下的木材总量 $\sum\limits_{i=1}^{N}\max(0,\,h_i-H)$ 至少为 $M$。
• 洛谷 P2440 木材加工：已知原木数量 $n$（$1\le n\le 10^5$）、所需小段总数 $k$（$1\le k\le 10^8$）和每根原木长度 $L_i$（$1\le L_i\le 10^8$），求最大的正整数 $l$（若不存在则为 $0$），使得 $\sum_{i=1}^{n} \left\lfloor \frac{L_i}{l} \right\rfloor \ge k$。
• 洛谷 P1182 数列分段 Section II：已知正整数 $N$（$1\le N\le 10^5$）、分段数 $M$（$M\le N$）和长度为 $N$ 的非负整数数列 $A_i$（$A_i<10^8$），求最小的整数 $S$（$S\le 10^9$），使得数列可被划分为 $M$ 个连续段，且每段和均不超过 $S$（即 $\min \max_{k=1}^M \sum_{i\in \text{第}k\text{段}} A_i$）。
• 洛谷 P2678 跳石头：已知起点到终点距离 $L$（$1\le L\le 10^9$）、中间岩石数 $N$（$0\le N\le 50000$）及其与起点的距离序列 $D_i$（$0<D_i<L$，严格递增），至多移走 $M$ 块岩石（$0\le M\le N$），求剩余岩石（含起点与终点）构成序列 $S$ 中相邻间距 $\text{gap}(S)$ 的最小值的最大值，即 $\max_{S\subseteq\{1,\dots,N\},\,|S|\le M}\;\min\;\text{gap}(S)$。题解：洛谷 P2678 跳石头 - Solution
• 洛谷 P1314 聪明的质监员：已知矿石数 $n$（$1\le n\le 2\times10^5$）、区间数 $m$（$1\le m\le 2\times10^5$）、标准值 $s$（$0<s\le10^{12}$），每个矿石 $i$ 有重量 $w_i$ 和价值 $v_i$（$0<w_i,v_i\le10^6$），以及 $m$ 个区间 $[l_i,r_i]$（$1\le l_i\le r_i\le n$），定义检验值 $y=\sum_{i=1}^m \left( \sum_{j=l_i}^{r_i} [w_j\ge W] \right) \cdot \left( \sum_{j=l_i}^{r_i} [w_j\ge W]\cdot v_j \right)$，其中 $W$ 为可选参数（整数），求 $\min_{W} |s-y|$。
• 洛谷 P1083 借教室：已知天数 $n$（$1\le n\le 10^6$）、订单数 $m$（$1\le m\le 10^6$）、每天可用教室数 $r_i$（$0\le r_i\le 10^9$）和 $m$ 个订单 $(d_j,s_j,t_j)$（$0\le d_j\le 10^9$，$1\le s_j\le t_j\le n$），按顺序处理订单，若存在最小编号 $k$ 使得 $\exists i\in[1,n]$，$\sum_{j=1}^{k} d_j\cdot[s_j\le i\le t_j] > r_i$，则输出 -1 和 $k$，否则输出 0。
• 洛谷 P4343 自动刷题机：已知日志行数 $l$（$1\le l\le 10^5$）、目标题数 $k$（$k$ 在 int 范围内）和每行操作 $x_i$（$-10^9\le x_i\le 10^9$），其中 $x_i>0$ 表示写 $x_i$ 行代码，$x_i<0$ 表示删除 $-x_i$ 行代码（若当前代码长度不足则全部删除），定义过程为初始代码长度为 $0$，依次执行操作，每次操作后若代码长度 $\ge n$（$n$ 为正整数）则提交并清零、题数加 $1$，求所有满足最终题数恰好为 $k$ 的 $n$ 的最小值和最大值，若不存在则输出 $-1$。

实数二分

• 洛谷 P1024 一元三次方程求解：已知实数系数 $a,b,c,d$，方程 $ax^3+bx^2+cx+d=0$ 在 $[-100,100]$ 内恰有三个不同实根，且两两之差的绝对值 $\ge 1$，求这三个实根，按从小到大顺序输出，精确到小数点后 $2$ 位。
• 洛谷 P1577 切绳子：已知绳子数量 $N$（$0<N\le 10000$）、所需段数 $K$（$0<K\le 10000$）和每根绳子长度 $L_i$（$0<L_i\le 100000.00$，实数），求最大的实数 $L$，使得 $\sum_{i=1}^{N} \left\lfloor \frac{L_i}{L} \right\rfloor \ge K$，结果保留到小数点后 $2$ 位（直接舍去 $2$ 位后的小数）。
• 洛谷 P1163 银行贷款：已知贷款原值 $w_0$、每月还款额 $w$ 和还款月数 $m$（$1\le w_0,w\le 2^{31}-1$，$1\le m\le 3000$），求月利率 $r$（以小数表示，输出 $100r$ 百分数形式，四舍五入到 $0.1\%$，且 $100r\le 300.0\%$），使得 $w_0 = w \cdot \frac{1-(1+r)^{-m}}{r}$。
• Codeforces 780B The Meeting Place Cannot Be Changed：已知朋友数 $n$（$2\le n\le 60000$）、初始位置 $x_i$ 和最大速度 $v_i$（$1\le x_i,v_i\le 10^9$），求最小时间 $T$，使得存在实数 $X$ 满足 $\forall i$，$|X-x_i|\le v_i\cdot T$（即所有 $n$ 个朋友可在同一地点汇合）。