自动搬运

查看原文

来自洛谷，原作者为

	StyWang **

搬运于2025-08-24 21:30:43，当前版本为作者最后更新于2018-05-03 14:01:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

概述

本文主要分析二分答案过程中，对于上下界的理解和实现。

我写二分答案时，上下界没有写好导致Wrong Answer。又看到讨论区有人的上下界写错了，于是TLE。所以决定仔细分析一下二分的上下界问题。

众所周知，二分答案时，需要有上界、下界、中点。分别命名为left,right,mid。

此题中，要求最大值，因此有重要结论：若mid为解，则最优解一定属于[mid, right]。若mid不为解，则最优解一定属于[right, mid)。对这部分不清楚的可以阅读这里，一篇很清晰地讲述二分答案的题解。

第一种理解

闭区间[left, right]为最优解存在的区间。

令mid = (left + right) / 2。

• 若mid为解（无论是否最优），则使left = mid. 此时不使left = mid + 1是因为mid可能是最优解，而最优解必须属于上述闭区间.

• 若mid不为解，则使right = mid - 1.

重复上述过程，直到闭区间只有一个值时跳出循环，即left == right。

但是，当left == right - 1时，mid = (left + right)/2 = left，则此次循环最后会使left = mid，程序陷入死循环。

出现死循环的问题，直接原因是整除的误差(3div2结果为1)，而根本原因是区间范围卡的过死。只有当left严格等于right时，我们才能宣布找出了最优解，又加之整除误差，因此在区间范围很小时，程序难以继续二分。

因此，我们需要把区间范围卡的“宽松”一点。

第二种理解

区间[left, right)为最优解存在的区间。

令mid = (left + right) / 2

• 若mid为解，则使left = mid.

• 若mid不为解，则使right = mid.

重复以上过程，直到right == left + 1跳出循环，left即为最优解。

这种区间的定义中，right为开区间，相比于闭区间较为“宽松”，有效避免了死循环的问题，代码可以AC。

但是，这两种理解方式区别很小，容易混淆，不建议使用，因此有了第三种更清晰的理解方法。

第三种理解

定义变量ans，储存当前优解。定义闭区间[left, right]，代表程序当前正在此闭区间内寻找答案（寻找潜在的比ans更优的解）（与前两种方法不同的是，最优解不一定要属于该闭区间）。

令mid = (left + right)/2

• 若mid为解，则ans = max(ans, mid), left = mid + 1.此时我们更新了最优解，同时在最优解的右侧寻找潜在的更有解。

• 若mid不为解，则right = mid - 1.mid不是解，因此我们在mid左边寻找更优解。

重复上述过程，直到left > right时跳出循环，ans即为最优解。

注意，当left == right时，也必须要在此区间内进行判断，因为当前还不能确定该区间内是否存在更优解。

代码：

//二分答案 
while(left <= right)
{
    int mid = (left + right) / 2;
    if(judge(mid))
    {
        left = mid + 1;
        ans = max(ans, mid);
    }
    else
        right = mid - 1;
}
printf("%d", ans);