二分优点,加快在有序数列中,蓝红区域的扩展,朴素算法缓慢进行.如何扩展,用灰色区域
的中点来判断,然后扩展颜色区域,灰色区域会不断减少,只要logn次就能把灰色区域长度
缩小为0
l在哪里,哪里就是蓝色,r同理,假设没有蓝色区域,赋值0(保留了一个位置)会导致,扩展过程中,红色一直扩展
直到两者相遇,l+1=r,导致错误(不满足条件),所以要指向数组两边
注意当l+1=r时候会退出循环体,不进行计算
注意细节,如果m处于最后一个元素边界更新时候越过中点可能会红蓝边界出错
出于正确性易懂性,写成l=m||r=m
注意分界线要保持唯一性,最后都会回到第一种情况
不看图--如何思考--红蓝对立
前提保证数据中一定有5的存在,没有分界线就不好找了(程序不好找)
做题思路,一开始先暴力枚举,过不了再优化
浮点数二分:for循环用小数会出现问题,递增控制在很小才能算出来,基本枚举不出来
考虑别的算法优化--二分,精度太高的时候,四舍五入下左右没有区别
二分答案模型
二分答案,最大化答案,最小化答案
最大化查找写成一个check函数,可行区内,返回真,l右移拓展,记住答案是x
最大化,越大越好,但不能超过条件,最小化,越小越好,但不能小于条件,输出答案为x,条件为y
y的条件并不一定取等号的时候取到x的最值,满足条件时候即可
x作为最短跳跃距离,不可能有比他还小的,从头到尾枚举一边把比他小的移开,大的保留
枚举跳跃距离不断二分就可以找到答案,模拟过程,累加计数
谁y谁x想哪个量随着哪个量变化.
差分技巧,把一段区间修改弄成两个点(头和尾,相加为0区间修改,目的是消除对后端的影响
然后求前缀和
最大值最小问题,x是伤害,y是走得通1,走不通0
标签：二分,--,扩展,笔记,枚举,区域,答案 From： https://www.cnblogs.com/zhoncai45/p/17670045.html