隐藏的二分

听说在这里写文章可以展示，我必须为了风瑾宝宝狠狠的写文章了。因为我只会信息竞赛所以只能写和竞赛有关的内容了 在高中数学里面就已经学到过二分了，是用于求函数近似零点的一种方式。由于log2的情况下可以将复杂度下降很多，因此很多问题在直接解决不成的情况下，二分是一个思考的方向。 很多题并不像解函数这种一眼就能看出来是用二分的，需要经验堆叠，另外也可以通过时间复杂度反推出需要使用二分再往这个方向上思考。以下是我最近做的题目中印象比较深的二分题，正好一个是实数一个是整数，分享一下。 实数的例子是一条直线(0,0)到(l,0)上有n个点，每个都会用vi的速度向外传播圆，求覆盖(h,0)到(h,l)直线的时间 这个题目的第一直觉是用一个算法去求出t，但是你会发现因为检测的点不确定，因此你并不确定是哪个点的距离除以哪个速度 然而，如果给你一个确定的时间t，你就可以知道每个点在(h,0)到(h,l)上覆盖的线段，通过线段合并（别的知识点）就可以判断是否可以覆盖。 因此定义l=0,r=MAX（一个很大的数），然后 while r-l>eps(一个很小的常数）: mid <- (r+l)/2 if check(mid)://判断mid是否可以全覆盖，是则返回true r=mid//寻找更小的可能 else l=mid end if end while 这样就可以通过对t时刻状态的分析变成在全局上寻找最小的t 而整数的例子简化后是这个：在一个长为l，深为h的地图上，有n次挖掘，每次从l到r的范围内挖1，问是否会挖穿，如果会是第几次的时候挖穿的？ 这个题目最简单的直觉就是模拟，每次从l到r循环给a[i]++。然而这样的话在数据大的时候每次都去操作r-l+1次的时间开支就太大了 同样，这里也有一个小知识是差分（前缀和的逆运算，可以理解成求导），只需要在d[]数组中标记d[l]和d[r]，就可以在n次操作后用的d[]数组推出a[]。 那么问题就是如何确认哪里的时候a[]数组有元素超过h了，这就可以交由二分解决 注意整数的时候需要仔细考虑边界条件，以下是我的例子： while l