二分答案专题
前言
- 本篇将总结几个二分答案的套路题
- 如果你还不知道什么是二分的活建议先从这里开始：
https://www.luogu.com.cn/training/111#problems - 这里写一下我常用的模板，本文基本套用此模板：
1 | // 设二分范围为 [L,R] 这里只讨论整数范围内的二分 是实数范围内注意需要控制精度 |
一点导论：
- 二分的本质是什么？ 我的理解是：将一个满足单调性的求解性问题转化为若干个判断性问题进行筛选进而求解
- 为什么必须满足单调？ 不如思考中学数学是怎么使用二分思想求解函数零点的——如果不满足单调则无法证明二分的正确性
- 二分的意义是什么？ 不二分仍然能通过从头到尾筛选进行求解，二分利用了问题的单调性将线性时间的尝试缩短到对数级别
- 为什么转换？ 因为有些问题不好直接求解答案，然而对于某个答案却很好判断其正确性(如果你做过一些二分就明白我在说什么)
- 二分的必要性： long long 范围内 $log10^{18}$ 也才 60 左右，所以你如果能够察觉到题目具有二段性(即单调性)，那么直接尝试思考最外层是一个二分答案！
- 要明确的一点是带有二分的题永远不是在考察二分，而是在于 check 函数的内容，check 里面可能是复杂的模拟贪心或是搜索甚至是 dp，如何写 check 则是考察综合算法能力，不在讨论范围内
- 很多题目长得就是一张要二分的脸。但是也有很多二分问题可能会带有一定的迷惑性，让你觉得这道题使用贪心或是 dp 就能够解决，所以本文旨在介绍几个模型，让你更容易首先发掘到这是一道二分问题
二分+单调队列
-
寻找段落 洛谷 P1419
-
题目大意：给定长度为 n 的序列 a，给定长度范围[s,t]，求长度在该范围内的连续子序列的平均值的最大值。即求$\frac{\sum_{i=start}^{end}a_i}{end-start+1} ,s\leq end-start+1 \leq t$ 的最大值
-
输入输出：给定序列长度 n 后给定 s 和 t，而后给出 n 个序列值$a_i$ ($n\leq 10^5,1\leq s\leq t \leq n,|a_i|\leq 10^4$) 输出一个保留三位小数的最大平均值
-
样例
1
2
3
4
5
6
7输入：
10
3 5
3 -1 4 -3 7 -3 4 -5 2 -1
输出：
2.667 -
分析：通过这道题你就应该能够明白我之前所说的“有些问题不好直接求解答案，然而对于某个答案却很好判断其正确性”，本题有两个关键巧妙的数学转换。
- 二分最大平均值，对于二分值 mid 将序列所有元素都减去 mid，然后判断序列中是否存在长度为 s~t 的序列和大于等于零即可(这里是一个重要的数学转换，与原问题等价)，如果不存在就说明平均值应该更小，反之答案应该更大
- 那么如何快速找出满足长度范围的序列和的最大值呢？我们可以先对减去 mid 的序列求出前缀和序列 sum，于是问题变成了判断 $sum_j-sum_i,s\leq j-i+1\leq t$ 的最大值是否大于等于零。求解时我们对 j 遍历，所以$sum_j$已知，问题继续转化为找到范围内最小的 $sum_i$
- 如何快速找到前面出现过的最小值呢？我们可以使用单调队列维护(单调队列可以在规定长度内维护最值)，时间复杂度控制在 O(n)，总时间复杂度为 O(nlogn)
-
代码
1 |
|
二分+bfs
-
刺杀大使 洛谷 P1902
-
题目大意：给定 n*m 的矩阵，其中$p_{ij}$为矩阵中第 i 行第 j 列的值，要求从第 1 行到达第 n 行(只能相邻走不能跳着走)，起点和终点可任意选取(但起点和终点必须分别为第 1 行和第 n 行中的某点)，对于任意一条抵达路径定义伤害值为该路径中的最大值，问从起点到终点的完整路径最少受到的伤害值为多少？
-
输入输出：给定 n,m 后给定 n*m 的矩阵值 $p_{ij}$ (n,m,$p_{ij}$<=1000) 输出一个数表示最小伤害
-
样例
1
2
3
4
5
6
7
8
9输入:
4 2
0 0
3 5
2 4
0 0
输出:
3 -
分析：这道题很容易会想到二分答案，那么对于每个二分值 mid 从起点跑一遍 bfs，过程中如果搜索点矩阵值 val[i][j]>mid 那么跳过它，最后用判断能否到达最后一行并以此作为 check 函数的返回依据即可 复杂度最坏 O(n*m*log(max $p_{ij}$)) 但实际上要小得多
-
代码
1 |
|
二分+dfs 图论
我的方法不是正解但仍然是过了 建议最后看一下正解
-
通往奥格瑞玛的道路 洛谷 P1462
-
题目大意：给定 n 个点 m 条边的无向图，每经过一条边损失相应血量，每经过一个点损失相应金钱，给定初始血量 b(途中血量不能为负)，问从 1 号点到 n 号点的路径中，所经过的所有点中最大损失的金钱的最小值是多少?如果到不了点 n 就输出“AFK”
-
输入输出：首先给定 n,m,b，接下来给定 n 个值 fi 表示经过点 i 需要缴费 fi，然后给定每条边的两端点和经过该边损失的血量 ai,bi,ci (n<=1e4 m<=5e4 b,ci,fi<=1e9) 输出最小损失值或“AFK”
-
样例
1
2
3
4
5
6
7
8
9
10输入:
4 4 8
8 5 6 10
2 1 2
2 4 1
1 3 4
3 4 3
输出:
10 -
分析："最大值的最小值"是不是很熟悉？带着这个题眼的十有八九都是二分答案！这道题跟上一道题几乎一样，唯一不同的是要多维护一个血量。这道题可以使用 dfs，在把血量维护在 dfs 参数中，还是上一题的模式，限定最大损失金钱 mid 判断能不能搜到终点 n。然而正解是跑 spfa 不过我的程序仍然过了，而且根据运行时间来看复杂度不算太糟糕但仍旧比二分+spfa 差了不少 最坏复杂度 O(n*m*log(max fi)) 但实际要小得多
- spfa 复杂度为 O(k*m) 实际上我的解法就是暴力版的 spfa 解法 (但如果 spfa 被卡了会退化成 O(n*m)
所以一样) - 低情商是我当时压根没想到 spfa，高情商是 dfs 可读性要比 spfa 好理解得多
- spfa 复杂度为 O(k*m) 实际上我的解法就是暴力版的 spfa 解法 (但如果 spfa 被卡了会退化成 O(n*m)
-
代码
1 |
|
二分+并查集
-
部落划分 洛谷 P4047 [JSOI2010]
-
题目大意：二维平面上给定 n 个点的坐标，现在要将 n 个点划分为 k 个非空集合，对于一种划分方法，定义两个集合的距离为两集合中直线距离最近的两个点，求出一种划分使得最近的两个集合距离的最大
-
输入输出：给定 n k，而后给定 n 个点的横纵坐标 $x_i y_i$ ( $n,k \le10^3$ , $x_i,y_i \le10^4$ ) 输出保留两位小数的最优划分最近的两个集合距离
-
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14输入:
9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3
输出:
2.00 -
分析：经典最大值的最小值，由于这道题需要维护集合因此我们可以使用并查集。我们对于最短距离进行二分答案，对于距离 mid，二重循环遍历每一个点对 $p_1,p_2$，如果 $p_1,p_2$直线距离小于 mid 且这俩点不在一个集合内就它们合并。最后看被划分了几个集合即可，如果对于 mid 来说集合数大于等于 k，那么显然可以继续让 mid 变小，否则需要将 mid 增大。总时间复杂度 O( $n^{2}*log(?)$ )，坐标最大值为 $10^4$ ，且本题二分需要在小数上二分精度要控制在 $r-l \ge 10^{-6}$，所以对数项最大约为 log( $10^{10}$ )
-
代码
1 |
|
二分+字符串哈希
这道题因为原数据量过小所以是个大水题，但题目本身很好，所以我们不妨思考一下数据量大时的算法
-
我在哪？ acwing 1460
-
题目大意：给定长度为 N 的字符串，找到最小的长度 k，使得原字符串中任意长度为 k 的连续子串都不相同
-
输入输出：给定长度 N，而后给出长度为 N 的字符串，输出最小满足题意的长度 k。 原数据只有$N\le100$，我们来思考$N\le10^5$时的解法
-
样例
1
2
3
4
5
6输入:
7
ABCDABC
输出:
4 -
分析：如果$N\le10^5$显然我们需要设计一个$NlogN$的算法，本问题显然满足单调性，即如果最终答案为 res，那么所有小于 res 的答案均不合法而大于 res 的答案全部合法，所以我们可以使用二分答案。那么如何快速判断对于长度 mid 原字符串是否有相同的字串呢？显然可以使用字符串哈希，预处理出原字符串哈希值，从前往后遍历算出所有长度为 mid 的哈希值，再判断是否有出现超过一次的哈希值即可，每次遍历 O(N) 总复杂度 O(NlogN)
-
代码
1 |
|
二分+贪心
贪心在二分中出现的题灰常灰常的多，像 leetcode 中几乎所有二分答案内核都是个贪心。由于篇幅原因本初仅选一题。
-
Match Points codeforces 1156C
-
题目大意：给定长度为 n 的序列和一个数 z，问序列中有最多多少对$i,j$ 满足 $|a_i-a_j|\geq z$，其中$i,j$不重复选择
-
输入输出：给定 n，z，然后给定 n 个序列值$a_i$ ($2\leq n\leq 2*10^5,1\leq z\leq 10^9$) 输出一个最大对数
-
样例
1
2
3
4
5
6输入：
6 4
17 13 16 12 15 11
输出：
3 -
分析：乍一看能直观的想到二分图最大匹配但是很遗憾数据量不允许。那么如何贪心呢？问题的关键在于对于$a_i$如果有多个$a_j$满足要求我们应该使用哪个$a_j$呢？如果你想的是按顺序最小的匹配最小的那就错了，比如 z=2 时有数据$2 5 7 8$ 答案是两对，但如果使用 2 匹配 5 那么只能凑出一对
- 先排序，然后二分答案长度 mid，我们只要判断前 mid 个( $a_1$ ~ $a_{mid}$ )和后 mid 个( $a_{n-mid+1}$ ~ $a_{n}$ )能否严格按顺序依次匹配即可，这里满足单调性
- 本题的贪心就体现在“前 mid 和后 mid 依次匹配”，而不是随便挑一个满足的匹配
- 为什么要判定时要严格按顺序呢？由于排序后序列单调不递减，如果前 mid 中的第 k 个数匹配不了后 mid 中的第 k 个数，即$a_{n-mid+k}-a_k>z$，那么如果想要匹配$a_k$则需要找到更大的数，即下标大于$n-mid+k$的，那么后面必然有一个无法匹配成功，因为后面 mid 个数长度为 mid，中间空出一个后面如果全匹配上那么长度必然为 mid+1 这显然是不可能的
-
代码
1 |
|
分数规划
- 分数规划是一个经典的使用二分求解的模型
- 该问题为给定一个长度为 n 的序列 $f_i,g_i$ 求 $\frac{\sum_{i = 1}^n f_i * x_i}{\sum_ {i=1}^n g_i * x_i}$ 的最大值 其中 $x_i$ 只能取 0 或 1
- 易证得该式对答案具有单调性，将其转换为二分问题设该式可能取值为 mid，我们现在要判断原式大于 mid 是否有解，则等式两边变换可得 $\sum_{i=1}^n(f_i -mid*g_i)*x_i\geq0$
- 最优解显然当 $f_i -mid*g_i$ 为正时令 $x_i=1$ 否则为零即可，如果这样取最后的总和都小于零则向小答案二分否则向大答案二分
分数规划+背包
-
Talent Show G 洛谷 P4377 [USACO18OPEN]
-
题目大意：每头奶牛都有重量值和才艺值两个属性，给定 n 头奶牛的重量值 $w_i$ 和才艺值 $t_i$ ，现在你可以任意选择其中的奶牛，使得选出来的奶牛总重量大于给定值 W(保证最初给出的 n 头总重量的和大于 W)，且需要让总才艺值和总重量的比值尽可能大。
-
输入输出：给定 n，W，然后接下来 n 行每行给出这头奶牛的 $w_i,t_i(1\leq n\leq 250 , 1\leq W \leq 1000 , 1\leq w_i\leq 10^6 , 1\leq t_i \leq 10^3)$, 输出 答案*1000 并向下取整的值
-
样例
1
2
3
4
5
6
7
8输入：
3 15
20 21
10 11
30 31
输出：
1066 -
分析：本题就是在分数规划的基础上加上了选择的限制，那么如何处理选择出的奶牛重量和大于 W 呢？在此基础上又如何算出最大比值呢？
- 对于比值我们没法直观的计算，那么我们使用分数规划的思想对答案进行二分，这样二分出的答案一定是最大的，但这样一定对吗？
- 本题中首先需要满足重量和大于 W，这个优先级是最高的，我们需要判断满足二分值的所有方案中的最大重量是否大于 W。这里有点困难，因为我们好像没法知道具体的选择方案。但是我们需要知道具体的方案吗？就像求解背包问题的时候我们根本不关心具体的方案，我们只关心最优的解是多少
- 上面介绍分数规划的时候如何取值的最优解呢？满足 $f_i -mid*g_i>0$ 就取，但在本题中如果都这样取不一定满足重量总和大于 W，反过来说如果要优先满足重量大于 W，那么要抛弃这种贪心的选法
- 对于 $f_i - mid * g_i$ 这个式子用本题的变量名字就是 $t_i - mid * w_i$ ，我们只需跑一边 01 背包即可，那么上式就是每个物品的贡献。dp 时对于重量大于等于 W 的都算在 dp[W]上(取 max，因为我们只需看 W 的情况)，那么最后只需要判断 dp[W]是否大于等于零即可
-
代码
1 |
|
