4.10 学习笔记之二分答案

发布时间 2023-04-10 10:01:43作者: Moyyer_suiy

啊,我不会二分。刚学。


 

二分答案,可以理解为二分答案所在的区间。

一般能使用二分答案的要求:1.有界性。2.具有单调性。

对于有界性:理解为答案一定在一个区间范围内,是固定的。

对于单调性:显然。这样才能找最优解。


 

简单来说,二分答案的题目,会出现“最小值最大” or “最大值最小” 的字眼。

思考,这种题目的一个暴力思想:枚举可能的答案,然后找到最优解。

根据二分的思想:我们大可不必枚举每个区间,而是每次找答案可能在的区间,找到其中间值 mid,如果 mid 符合要求,那么会往该区间的右侧去看:是否能找到更优解(体现了单调性);反之,不符合要求,我们往 mid 的左侧去看,去找那个能满足要求的。

在判断是否满足条件时,不需要考虑限制,直接模拟,最后判断是否符合要求即可。

这样,在枚举答案时就避免了很多没用的区间。


 

综上,二分答案的题目具有一定模板性,分为以下几步:

1.确定当前判断的区间。

2.一个 check 函数模拟判断。

3.满足:向右找最优;不满足:向左找满足。


 

但时对于二分答案,一定一定需要注意的是,判断边界条件。建议动动脑子,根据题目特性。一般分两种写法,l <= r 是一种,l < r 是另一种。N 老师提倡后者,但我认为前者对我来说更好理解,所以选择前者。