Loading... 顾名思义，二分答案“二分”的是“答案”。弄清楚了这点，思路就很清晰了。我第一次接触时，就弄不清到底要二分什么。其实，如果你可以判断一个给出的结果是否正确，那么就应该将二分答案放在解题首选位置了。 我们什么时候能用二分答案呢？当题目要求“最大的最小值”或“最小的最大值”时。当然，你还需要一个范围。只不过由于二分极其高效，右边界大一些，对时间的影响不大。 下面是常用的二分答案格式。 ```cpp while(l+1 < r){ mid = (l+r)>>1; if(judge(mid)) l = mid; else r = mid; } ``` ## 题解 [P2678 跳石头](https://www.luogu.com.cn/problem/P2678) 这是一道近似于模板题的经典二分答案题。 我们只需对“最短跳跃距离的最大值”进行二分。左端点设为1，右端点不小于起点到终点的距离。 ### 代码 ```cpp #include <cstdio> int len, n, m, a[50001]; bool judge(int x){ int dels = 0, last = 0; for(int i = 0; i < n; ++i){ if(last+x > a[i]) ++dels; else last = a[i]; } if(len-last < x) ++dels; return dels <= m; } int main(){ scanf("%d%d%d", &len, &n, &m); for(int i = 0; i < n; ++i){ scanf("%d", a+i); } int l = 1, r = len+1, mid; while(l+1 < r){ mid = (l+r)>>1; if(judge(mid)) l = mid; else r = mid; } printf("%d\n", l); return 0; } ``` ## 题解 [P1577 切绳子](https://www.luogu.com.cn/problem/P1577) 同样是二分“切割后每条绳子的最大长度”。于上面的题不同之处在于此题涉及浮点数精度问题。循环条件可以写成如下面代码所示的`l+1e-3 < r`形式，也可以固定循环次数。 ### 代码 ```cpp #include <cstdio> int n, k; double a[10001], maxL = 0; bool judge(double x){ int tot = 0; for(int i = 0; i < n; ++i){ tot += a[i]/x; } return tot >= k; } int main(){ scanf("%d%d", &n, &k); for(int i = 0; i < n; ++i){ scanf("%lf", a+i); if(a[i] > maxL) maxL = a[i]; } double l = 0, r = maxL, mid; while(l+1e-3 < r){ mid = (l+r)/2; if(!mid) break; if(judge(mid)) l = mid; else r = mid; } printf("%.2lf\n", (int)(r*100)/100.0); return 0; } ``` 浮点数的二分也可以这样写。固定二分次数，不断缩小范围。 ```cpp for(int i = 0; i < 100; ++i){ mid = (l+r)/2; if(judge(mid)) l = mid; else r = mid; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
