一本通提高篇学习笔记-二分答案

二分是一种常用并且非常精妙的算法。经常是解答问题的突破口。它的基本用途是在一个单调序列或者单调函数里面做查找操作。当问题不易求解答案而易于验证答案,且答案空间具有单调性和有界性,此时就是二分的最佳时机。


二分的概念与写法

我曾经在洛谷P2678跳石头一题的题解中写下如下文字:

我们把这个方法叫做“二分答案”。顾名思义,它用二分的方法枚举答案,并且枚举时判断这个答案是否可行。但是,二分并不是在所有情况下都是可用的,使用二分需要满足两个条件。一个是有界,一个是单调。

二分答案应该是在一个单调闭区间上进行的。也就是说,二分答案最后得到的答案应该是一个确定值,而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性,那么这个单调性应该体现在哪里呢?

可以这样想,在一个区间上,有很多数,这些数可能是我们这些问题的解,换句话说,这里有很多不合法的解,也有很多合法的解。我们只考虑合法解,并称之为可行解。考虑所有可行解,我们肯定是要从这些可行解中找到一个最好的作为我们的答案, 这个答案我们称之为最优解。

最优解一定可行,但可行解不一定最优。我们假设整个序列具有单调性,且一个数x为可行解,那么一般的,所有的x’(x’<x)都是可行解。并且,如果有一个数y是非法解,那么一般的,所有的y’(y’>y)都是非法解。

那么什么时候适用二分答案呢?注意到题面:使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西,那么这个东西应该就满足二分答案的有界性(显然)和单调性(能看出来)。

今天要整理的东西,和上文相似而又略有不同,同时也算是当作一次简单的复习和“预习”——lk大佬明天要讲解二分算法。

二分法的思想就是不断将待求解区间不断分成两份,根据求解区间中点的情况来确定目标元素所在的区间,这样就能把解的范围缩小一半又一半。

在使用二分法解决类似问题时,类似于在考虑一个布尔表达式E,在问题定义域[L,R]内存在一个分界点J:


∀L≤x≤J,E(x) = true

 ∀J<x≤R,E(x) = false

定义域为整数的情况还是比较常见的。不过也存在定义域为实数域的问题。在这样的区间进行二分时通常需要定义一个最小精度eps,通过判断R-L的精度是否达到要求来控制二分。但是由于C++实数的精度问题,eps没办法取得很小,如果eps取值过小的话会造成死循环。其实,指定一下二分次数也是一个不错的方法。

整数域上二分答案模板:

1
2
3
4
5
6
7
8
9
10
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
//最后的答案是ans

实数域上二分答案模板:

1
2
3
4
5
6
7
8
while (fabs(l - r) > eps) {
mid = (l + r) / 2.0;
if (check(mid))
r = mid;
else
l = mid;
}
//最后的答案是l

如上所述,如果指定二分的次数为t,那么对于初始的求解区间长度L,算法结束后r-l的值会是L/2t,根据这个值判断精度是否达到要求即可。

二分答案的用途

求解各种最大值最小,最小值最大问题。用二分答案确定答案后,再采用其他算法判定该解是否合理。就可以将最优化问题转换成判定性问题。

二分查找。用具有单调性的布尔表达式求解分界点,比如在有序数列中求x的排名。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:一本通提高篇学习笔记-二分答案

文章作者:Shawn Zhou

发布时间:2018年12月11日 - 18:12

最后更新:2019年01月18日 - 19:01

原始链接:http://shawnzhou.xyz/2018/12/11/18-12-11-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。