做了一些二分的题目,对这类题目还是有些害怕,希望整理过后可以做的好一点吧
二分的实质是找到一个边界,左半边满足这个性质,但右半边不满足这个性质(并不一定要满足单调的条件)
存在一个分界点 $p$,使得 $[l,p)$中的数都是非法解,$[p,r]$中的数都是可行解。
而 $p $即为所求的最小解。
这里的左/右边界分别都是第一个不满足判断条件的点
这种性质启示我们用一种特定的方法来枚举答案,于是有了二分。
注意:当题目出现XX最短/最小的最大值或者XX最长/最大的最小值,就要想到二分
- 情况一(求左区间的右边界)
当check函数成立的时候,此时mid处于红色区间(左区间),mid满足check,所以直接l = mid
当check函数不成立的时候,mid处于绿色区间(右区间),此时mid不满足check函数,所以需要减1向左侧靠拢r = mid - 1
注意:这种情况的mid需要加一,mid = l + r + 1 >> 1
(如果l = mid
就要+1
)
代码:
mid = l + r + 1 >> 1
while l < r:
if check():
l = mid
else:
r = mid - 1
- 情况二(求右区间的左边界)
当check函数成立的时候,此时mid处于绿色区间(右区间),mid满足check,所以直接r = mid
当check函数不成立的时候,mid处于红色区间(左区间),此时mid不满足check函数,所以需要加1向右侧靠拢l = mid + 1
代码:
mid = l + r >> 1
while l < r:
if check():
r = mid
else:
l = mid + 1
刷题体会:
观察题目,只要出现了求所有最大值的最小值或最小值的最大值或能抽象出这个条件的,十有八九是二分。。
感觉做题的关键在check
函数上,只要想到check
函数怎么写,就能做出来
题目中一般会给出一些限制条件,就比如跳石头 中至多从起点和终点之间移走$M$ 块岩石,路标设置中最多可增设的路标数量$k$等等。
这些就是check
函数的判断条件捏
经常会做到check()
函数对应的值的和二分的答案是相反的关系,比如check()
函数求的是分组的数量,但二分的是每组的长度,由于分组数量越多,则意味着每组长度越短,所以在求解时需要注意二者的转换。
有些时候check()
还会出现一些特殊情况,比如在分组的时候,可能会恰好少了一组等,做题时需要注意。
刷题列表:
洛谷 P2249. 【深基13.例1】查找
模板题
洛谷 P1102. A-B 数对
模板题,也是通过二分求某个数在列表的起始编号与结束编号,二者相减再加一就得出答案。
洛谷 P2440. 木材加工
本题出现了能够切割得到的小段的最大长度。
把题目提供的需要的小段数量作为check()
函数的判断条件,通过二分求得的小段长度判断切出来的数量是否超过了需要的或者还不到。
洛谷 P2678. 跳石头
本题出现了最短跳跃距离的最大值。
移动石头的数量有上限,对于二分求得的最短距离和每块石头之间的距离进行比较,如果无法完成跳跃,那么就把石头挪走,如果挪走的石头没有超过已知的上限,那么check
函数返回True,如果超过了上限,则返回False。
洛谷 P1678. 烦恼的高考志愿
利用二分找到最接近学生成绩的分数线并计算即可
洛谷 P3853 路标设置
分析题目可知求最大值在不同情况下的最小值。
二分答案($x$)之后看每一段区间长度内需要放几个路标,res += (old[i + 1] - old[i]) // x
但存在一个特殊情况,如果某一段区间长度能被空旷指数$x$整除,比如这一段区间长度是$10$,$x$是$5$,按照公式应该要摆放两个路标,但其实只要拜访一个就行。
所以需要特判:
if (old[i + 1] - old[i]) % x == 0:
res -= 1
洛谷 P1182 数列分段 Section II
本题同样提到了最大的和最小这一点。
那么就可以通过二分这个最大的和,以不超过这个和为条件在check()
函数中进行分组,看能分几次。
这里采用了贪心的思想,对于每一个元素,看他是否能塞进前一个组里,如果可以就塞进去同时让这个组的和加上这个元素,如果不行就重新开一个数组,让新数组的和就等于这个元素(就错在这里了,直接把新数组的和置为0了)。
但需要注意的是,这样的分组并没有考虑到最后一组的,她根本没有被计算进去。
因为这里res
的计算方式是,只有超时了才会re += 1
。
因此最后还需要再让res += 1
二分跟着y总板子理解,多做题感觉就容易了,我之前也恐惧二分QAQ
加油qaq