二分总结
小注意:此总结仅其发源于做题的灵感,并非以一盖全
二分模板
其实所谓的二分模板并不需要死记硬背,通过以下注释可能有助于你去理解记忆
int l = 0, r = n - 1;
while (l < r)
{
// 法一记忆方法:由于在mid中是往下取整的对于l(左)来说少了1,因此不公平l = mid + 1取多一个数
int mid = l + r >> 1; // 相当于 / 2
if (check(mid, ...)) r = mid;
else l = mid + 1;
// 法二记忆:联合上面的,动过一次l了,那么这次动的就是r。由于这次是往上取整,因此对于r来说少了1,r = mid - 1 多取一个数
int mid = l + r + 1 >> 1; // 相当于 / 2
if (check(mid, ...)) l = mid;
else r = mid - 1;
}
对于用哪个模板。实质上我们还是要看判断,具体的要看是我们的目标是让 l = mid
还是r = mid
,也就是说在写代码的时候,把= mid
这个判断条件作为最后的输出结果的导向。
二分规律总结
本质规律
- 找到分界点,即二分在什么地方?即
check()
的点 - 再去观察是否有得通过常见规律获得线性数列(常常是递增或者递减)
因此可以认为二分其实最应该先做的是去找一个存在非此即彼的存在
但是我们知道其实二分对于线性
&& check()
二者都是缺一不可的
二分题目实例
二分其实最难的点就是去找到这种非此即彼的存在,即使说有注意到但是很多情况之下算法题有太多的非此即彼的关系,比如
int a; // a <= 0 or a > 0
其实即使说简单到只是一个a的大小判断可能都会成为我们的check()
的判断条件
但是也可能达到很难的,比如
- 在某个进制下,大于b的进制表示下:n个小于连续i个1的数;小于b的进制表示下:n个大于连续i个1表示的数
做题的一些小方法
- 前缀和常常联系到二分:joy:或者说二分常常联系到前缀和
- 这一点是关键的,在做出来的二分也就是拿到
l
或者r
之后,要进行判断这个东西是否符合条件 - 从问题导向(他要什么我们就给什么。既然我们的目标是从这个入手,那么二分很有可能就是用在上面):题目所问的其实很有可能就是最终二分的目标对象,这个时候去看一下有没有可能在目标对象上面存在线性的关系,如果有可能就可以考虑用二分,因此可以从此观察check()与线性关系
例题
(带着注释的思想取把题目在思考一下)
- 一维:某个数
(x)
在数列中出现的次数
sort(nums.begin(), nums.end());
// 找到左边的第一个数:第一个 >= x
l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] < x) l = mid + 1;
else r = mid;
}
// 找到右边的即最后一个数:最右边 <= x的数
l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (nums[mid] <= x) l = mid;
else r = mid - 1;
}
- 三体攻击:https://www.acwing.com/problem/content/1234/
问题导向
可以建立到三维 → 一维的空间,然后也可以存下来所有的攻击,但是发现最后如果枚举所有攻击的时候发现是出问题的
这个时候最关键的就是找到发现打击力度是叠加的,然后我们要找到第一次破防的那个飞船
// 由于打击的力度是叠加的,题目问的是找到至少第几次打击会造使范围内防御力最低的首先破防
// 因此我们可以认为,没打击时打击的力度为0,打击完后对于某个范围内的目标的他的总力度为n
// 可以对按顺序二分进行每次打击的观察,然后check()对某范围的打击过后,该范围内的某个家伙是否首先破防了
- 四平方和:https://www.acwing.com/problem/content/1223/
第一眼红尘微透:暴力呗(杯),枚举所有四次的各个数的平方找到合适为止
第二眼看破:很明显这样是不行的,但如果当前的数是由a、b并且满足a <= b的,那么就可以通过枚举a,然后找到大于a的数的上限(题目给定了5 * 1e6的开方 ≈ 2500
)此时,就可以通过二分找到b
然后很明显是找得到两个数的平方和也就是(0 ~ 2500) * (0 ~ 2500)
的所有可能,然后存储起来这些可能的值即可
// 5 = 02 + 02 + 12 + 22
- 分巧克力:https://www.acwing.com/problem/content/1229/
对于一块巧克力的所有分法是可以存下来的,但是我们只要把他当前的这个分法的个数给存下来即可,因此最终遍历数组找到最大的分发即可
但是我们发现分成某一种分法存在n²
级别,并且这种分法是一种很暴力的每一种都尝试去做一下分割,因此不能对所有的单独分
问题导向:我们发现有一个东西很不错就是最终的边长是存在最小跟最大的,而我们要得到的也是所有之中最长的边长。因此可以考虑从小到大去找找某一条边是否符合我们的可以分的方法。这个时候把所有的巧克力都存储下来,再而去把他们对于当前这条边去分能分成多少块即可。
- 机器人条约问题:https://www.acwing.com/problem/content/732/
依旧是问题导向:既然目标是通过找到某个最小的值,而这个最小的值在一定的范围之内,因此通过二分找到当前的这个值即可