二分总结
本文最后更新于 2022年1月8日 下午
序
以前学习二分的时候一直没有搞清楚什么时候
整数二分的两种情况
第一种
这种情况代码如下
为什么
因为整数的除法是向下取整,我们需要在运算时+1时它变成向上取整,否则的话会因为边界问题导致while无限循环。
举个例子,在区间只有两个数的时候,比如,这时候如果check成功,那么会执行 ,然后问题就来了, 和 本来就都等于3,然后就会无限循环下去, 和 的值永远不会更新。所以在 的更新方式下,我们需要将运算时 成为向上取整才不会死循环。
第二种
这种情况代码如下
为什么
因为边界问题不会影响到值的更新,还是用上面那个例子,
。
此时如果check成功,那么,更新成功。如果check失败,则 ,同样更新成功。由此可以看出,在 的更新方式下,不需要对 进行任何操作。
以上是整数二分的两种固定写法。那么什么时候用哪种方法呢,这就要根据具体的题目进行分析了。
例题—— 分巧克力
题目描述
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足:
形状是正方形,边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数和 。
输入保证每位小朋友至少能获得一块的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
输入输出样例
输入#1
2 10
6 5
5 6输出#1
2AC代码
题目很简单是二分的板子题,主要是说为什么要用第一种求
为什么二分里面不能写成
推导一遍发现,如果
成立后,说明当前的 值也是在答案范围中,所以答案只能在 之中取。理所当然无法用上面那种写法,如果用上面那种方法, 会直接更新成 ,会越过 这个值,所以在一些情况就会出现错误,比如题面的样例 就会成为 ,越过了 这个可能的答案值,恰好 就是最大的一个答案,导致答案错误。
总结
这次弄明白了二分的写法属实是不易,留文一篇防止日后遗忘
以后写二分的时候记得注意一下区间情况