二分和三分

简介

当我们提到二分时，有两种可能的含义

在有序数组中寻到一个数字出现的位置，往往可以用 lower_bound 替代
直接求解困难，但是因为有单调性可以转化为判定问题
1. 答案是整数（第一类问题是特殊情况
2. 答案是实数

整数二分

int L = 0; // 左边界，需保证check(L) == true
int R = 1000000000; // 右边界，需保证check(R) == false
// 实际上永远不会检查初始的这2个位置，
// 所以有可能需要把左边界设为-1。

while (L < R - 1) {
    int M = (L + R) / 2;
    if (check(M)) {
        L = M;
    } else {
        R = M;
    }
}
// 此时L == R - 1, check(L) == true, check(R) == false;

实数二分

根据经验，控制二分次数的写法较好。每二分十次，可以获得三位精度(1/1024)。

double L = 0; // 左边界
double R = 1e9; // 右边界
for (int _ = 0; _ < 100; _++) {
    double M = (L + R) / 2;
    if (check(M)) {
        L = M;
    } else {
        R = M;
    }
}

（实数）三分

三分可以用于函数求最值，函数必须严格单峰，才可以三分。
和实数二分类似，也应该控制次数。

// 最大值
double L = 0; // 左边界
double R = 1e9; // 右边界
for (int _ = 0; _ < 100; _++) {
    double LM = (L + L + R) / 3;
    double RM = (L + R + R) / 3;
    if (calc(LM) < calc(RM)) {
        L = LM;
    } else {
        R = RM;
    }
}

可以发现这样每计算两次calc的值，可以将区间缩为原先的 $2/3$ 。
一个简单的想法是，既然函数是严格单调的，那只需要比较(L + R) / 2) - eps和(L + R) / 2) + eps即可，这样每计算两次calc的值，可以将区间缩为原先的 $1/2$ 。

一个更优秀的做法是比较 $L + (R - L) / \varphi, R - (R - L) / \varphi$ 两个点。
其中 $\varphi = \frac{1 + \sqrt{5}}{2}$ 。这样相邻两次三分，有一个公共点可以重复利用，可以大大提高效率。

除了第一次之外，每计算一次calc的值，可以将区间缩为原先的 $\frac{\sqrt{5} - 1}{2} = 0.618$ 。

STL

二分可以用于计算一个数字在有序数组中位置。
STL中有lower_bound，upper_bound可供使用。

如果只需要判断是否出现，也可以使用binary_search

参考题目

P1314

https://www.luogu.org/problemnew/show/P1314
二分，计算前缀和验证。

P1083

https://www.luogu.org/problemnew/show/P1083
二分，然后相当于执行一些区间减法，计算有没有位置变为负数，用差分和前缀和即可。

P1182 数列分段 Section II

https://www.luogu.com.cn/problem/P1181
https://www.luogu.com.cn/problem/P1182
二分，把问题转化为要求每段和小于等于 $x$ ，最少需要几段。
显然 $x$ 越小，段数越多。

存在一个值 M
< ans, 都无法划分为M段

= ans, 都可以划分为M段

P4403 [BJWC2008]秦腾与教学评估

https://www.luogu.com.cn/problem/P4403
直接所有数字异或，或者二分判断前缀中是否有奇数个1

P6003 [USACO20JAN]Loan Repayment S

https://www.luogu.com.cn/problem/P6003
整数二分，二分X
对于Y相同的天一起计算，至多有sqrt(n)个不同的Y。
总时间复杂度 O(sqrt(n) log(n))

P6099 [USACO19FEB]Dishwashing G

https://www.luogu.com.cn/problem/P6099
5
4
5
2
3
1

将4放入第一堆
将5放入第二堆
将2放入第一堆
洗2
将3放入第一堆
洗3
洗4
洗5

P6004 [USACO20JAN]Wormhole Sort S

https://www.luogu.com.cn/problem/P6004
https://wwwwodddd.com/usaco-2020-jan/
S3的代码还是有问题

https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P6004.cpp
可以用类似于双指针法的方法做

P3611 [USACO17JAN]Cow Dance Show S

P2115 [USACO14MAR]Sabotage G

P1024 一元三次方程求解

一元三次方程求零点
三分

P2759 奇怪的函数

P2619 [国家集训队]Tree I

WQS二分

求选择 $k$ 个的最优解，不方便直接求解。

二分一个权值 $v$ ，使得每选一个，可以额外获得 $v$ 的权值。

显然 $v$ 最优解中的个数是单调的。

二分 $v$ 来确定最优解。

CF163B

https://codeforces.com/contest/163/problem/B
二分控制次数的开始

CF1628A Meximum Array

给定一个长度为 n 的序列 a，分成任意个子数组，每个子数组的值为子数组中的数的 MEX 值，求这些子数组的值组成的序列中字典序最大的一个。