二分答案

二分答案

结合洛谷P2678 跳石头

“二分答案”。顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行。但是，二分并不是在所有情况下都是可用的，使用二分需要满足两个条件。一个是有界，一个是单调。

二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性，那么这个单调性应该体现在哪里呢？

可以这样想，在一个区间上，有很多数，这些数可能是我们这些问题的解，换句话说，这里有很多不合法的解，也有很多合法的解。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案， 这个答案我们称之为最优解。

最优解一定可行，但可行解不一定最优。我们假设整个序列具有单调性，且一个数x为可行解，那么一般的，所有的x'(x'y)都是非法解。

那么什么时候适用二分答案呢？注意到题面：使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。

那就好办了。我们二分跳跃距离，然后把这个跳跃距离“认为”是最短的跳跃距离，然后去以这个距离为标准移石头。使用一个judge判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的右边二分。为什么去右边？答案是，这个区间是递增的 ，而我们求的是最短跳跃距离的最大值，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。整个过程看起来很像递归，实际上，这个过程可以递归写， 也可以写成非递归形式，我个人比较喜欢使用非递归形式。

下一个问题，这个judge怎么实现呢？judge函数每个题有每个题的写法，但大体上的思想应该都是一样的——想办法检测这个解是不是合法。拿这个题来说，我们去判断如果以这个距离为最短跳跃距离需要移走多少块石头，先不必考虑限制移走多少块，等全部拿完再把拿走的数量和限制进行比对，如果超出限制，那么这就是一个非法解，反之就是一个合法解，很好理解吧。

可以去模拟这个跳石头的过程。开始你在i(i=0)位置，我在跳下一步的时候去判断我这个当前跳跃的距离，如果这个跳跃距离比二分出来的mid小，**那这就是一个不合法的石头，应该移走。**为什么？我们二分的是最短跳跃距离，已经是最短了，如果跳跃距离比最短更短岂不是显然不合法，是这样的吧。移走之后要怎么做？先把计数器加上1，再考虑向前跳啊。去看移走之后的下一块石头，再次判断跳过去的距离，如果这次的跳跃距离比最短的长，那么这样跳是完全可以的，我们就跳过去，继续判断，如果跳过去的距离不合法就再拿走，这样不断进行这个操作，直到i = n+1，为啥是n+1？河中间有n块石头，显然终点在n+1处。（这里千万要注意不要把n认为是终点，实际上从n还要跳一步才能到终点）。

模拟完这个过程，我们查看计数器的值，这个值代表的含义是我们以mid作为答案需要移走的石头数量，然后判断这个数量 是不是超了就行。如果超了就返回false，不超就返回true。

注意：以上内容非原创，但是不记得以前在哪看到的

二分答案过程中的上下界问题

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

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

此题中，要求最大值，因此有重要结论：若mid为解，则最优解一定属于[mid, right]。若mid不为解，则最优解一定属于[left, 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即为最优解。（可以确定left为最优解，但并不是最后一次二分的mid就是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);

注意：以上内容非原创，但是不记得以前在哪看到的