二分法转化为判定问题

发布时间 2023-10-19 10:27:59作者: shalins

题目:

 地址:https://www.acwing.com/problem/content/104/

这道题的二分性体现在平均值的最优性中

假设最大值为MAX,我们当前要判断的值为MID

当MID > MAX时,我们在当前条件下一定找不到符合假设的解,从而判断出比MID大的值全部无效。

当MID < MAX时,我们可以找到符合题意的解,那么小于MID的值也一定符合题意,也就不用再判断了。

 

判断一个值是否有符合题意的解,一般用check函数:

 在求前缀和的式子中,最后减去avg是面对平均数有关问题的常用解决方法,将原来判断大于一个值的问题转化为判断是否 >0 的问题。

当求前缀和时,一般从1开始循环,这样当i=0时,其值自动为0,省去了考虑数组边界的问题。

 

双指针技巧:在check函数的第二个for循环中,我们用两个指针来求某两个位置之间的前缀和的差。

但是题目中的要求是至少包含F块土地,所以sum[ i ]并不一定是sum[ j ]的比较对象,因此只有在当前的sum[ i ] < minv时,才会更新minv,否则就继续使用之前的值。  

 

主函数:

在实数的二分中,若题目要求保留k位数据,则我们一般讲while循环的条件设置为1e-(k+2)

且因为题目中要求的是向下取整,则我们最后的输出中必须时r * 1000,因为L < mid < r。

所以L向下取整得到的答案会有误差。