二分答案：模板速切指南

阅读之前

请确认您能够独立写出二分搜索的内容。

概述

前文说过，二分答案题的本质其实都是套路的打暴力，之后利用取值区间的单调不减性质，采用二分的方法将时间复杂度从 $O(N)$ 打到 $O(logN)$ 。

不同于二分查找的多种情况，二分答案的题模板是固定且单一的，我们只需要修改判断条件的部分即可下面我们来分析一下二分答案的板子。

板子

二分答案整数型最优模板如下：

int pv_l = 0, pv_r = arr[N - 1];
while (pv_l <= pv_r)
{
    int remain = M;
    int mid = pv_l + (pv_r - pv_l) / 2;

        // 生成condition，唯一需根据题意来写的地方
        // 其实说明白了这儿就是个纯粹的暴力

    if (condition <= 0)
        pv_l = mid + 1;
    else if (condition > 0)
        pv_r = mid - 1;
}

cout << pv_r << endl;

首先，对于单调不减的区间 $I$ ，我们放置左指针pv_l在区间开头，右指针pv_r在区间结尾。

初始

接下来，我们通过不断地收缩指针来减小可能的范围，非二分情况下，pv_l每次向左移动1，pv_r每次向右边移动1，则遍历数组需要的时间为

O(N)

。那么，我们每次取mid = (pv_l + pv_r) / 2，判断取得mid的情况下条件是否成立，然后以此为依据来移动左右指针，这样保证每次指针移动的距离可以达到数据长度的一半。

假设左侧收缩

于是只需要对数时间 $O(logN)$ 即可对区间完成搜索。事实上，此时pv_l在mid +1的位置上。因为mid是取不到的，将指针直接移动到mid后面即可。至于为什么结束条件是!pv_l <= pv_r是因为最后有个“试探”过程，代码中condition <= 0在condition == 0时进行了一次试探，直到pv_l > pv_r，此时pv_r没做试探，打印输出pv_l即可。

就这样说有亿些抽象，我们来通过例题练习下二分快速打板。

例题

A. 砍树（普及/提高-）

题述
伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$ （米），伐木机升起一个巨大的锯片到高度 $H$ ，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$ ，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$ ，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$ ，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式
第 $1$ 行 $2$ 个整数 $N$ 和 $M$ ， $N$ 表示树木的数量， $M$ 表示需要的木材总长度。
第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式
$1$ 个整数，表示锯片的最高高度。

分析
这个题需要明确的是，锯片越高，切下来的越少，否则越多。本质上，我们可以累加切下来的所有木头的高度总和。

灰色为锯片

求最值，可以想二分答案。考虑单调不减区间

[max(A),10^9]

，其中A是存储所有树高度的数组。想最直接暴力的法子，给定锯片高度

x

，如果

x>M

，则砍的还不够，需要砍的更多，更新右指针；否则如果

x\leq M

，则说明砍的超过了所需，更新左指针升高高度。因为此题要求尽量高，根据贪心思想，则把等于号放在这个区间试探，最后打印不用于试探的pv_l。之后按照这个思路二分找答案即可，非常明显的模板套用思路：

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

int arr[100001];

int main()
{
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    int pv_l = *max_element(arr,arr+N), pv_r = 1e9;
    while (pv_l <= pv_r)
    {
        int count = 0, tot = 0, mid = pv_l + (pv_r - pv_l) / 2;
        for (int i = 0; i < N; ++i)
        {
            if (i == N - 1 && tot + arr[i] == mid)break;
            if (i == N - 1 && tot + arr[i] != mid)count++;
            if (tot + arr[i] <= mid)
                tot += arr[i];
            else
            {
                tot = arr[i];
                count++;
            }
        }

        if (count <= M)
            pv_r = mid - 1;
        else
            pv_l = mid + 1;
    }

    cout << pv_l << endl;
    return 0;
}

B. 跳石头（普及/提高-）

题述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，距离为 $L$ ，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式
第一行包含三个整数 $L,N,M$ ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$ 。
接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$ ，表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式
一个整数，即最短跳跃距离的最大值。

分析
还是老话，先打穷举。我们先画个图表示一下样例数据：

样例数据

显然有局部 = 最优，观察局部情况。局部：移除掉所有间隔最小的距离中间那块石头，所有挪掉两块（题给数据）石头之后情况如下：

解答

即此时最小距离的最大值为

4

。那么我们可以设最小距离

x

，那么显然

x

最小值为1，根据贪心当所有石头平均分布时

x

取得最大值

L/(N-M)

。则从从0到

L/(N-M)

穷举

x

的值。也就是说，本题中的单调区间就是

[1，L/(N-M)]

。

以上就是二分中的条件，思路同上，我们通过不断合并区间来判断指针应该如何移动，合并：∃ $l$ < $x$ ，那么不断的将 $l$ 与后面区间进行合并，直到 $l\geq x$ 。每一次合并事实上都是移走了一块石头。之后比较合并次数与可以移走的石头块数。

还是一模一样的打板，一模一样的贪心：如果 $count <= M$ ，说明可以移走更多块，移走更多块就可以让距离变得更大，最小距离的最大值增大，右移左边界，那么等于号就放在这里进行试探；如果 $count > M$ ，说明已经超限了，需要移动更少的石头，最小距离的最大值减小，左移右边界，最后打印不用于试探的pv_r。

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

int arr[50001];

int main()
{
    int L, N, M,now = 0,before = 0;
    cin >> L >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        cin >> now;
        arr[i] = now - before;
        before = now;
    }

    arr[N] = L - before;

    if (N == M)
    {
        cout << L;
        return 0;
    }

    int pv_l = 1, pv_r = L / (N - M);

    while (pv_l <= pv_r)
    {
        int count = 0,temp = 0;
        int mid = pv_l + (pv_r - pv_l) / 2;

        for (int i = 0; i <= N; ++i)
        {
            temp = arr[i];
            while (temp < mid && i <= N)
            {
                i++;
                count++;
                temp += arr[i];
            }
        }

        if (count <= M)
            pv_l = mid + 1;
        else
            pv_r = mid - 1;
    }
    cout << pv_r << endl;
    return 0;
}

C. 小鸟的设备（普及/提高-）

题目描述
小鸟有 $n$ 个可同时使用的设备，第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。
同时小鸟又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。
小鸟想把这些设备一起使用，直到其中有设备能量降为 $0$ 。所以小鸟想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

输入格式
第一行给出两个整数 $n,p$ 。
接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$ 。

输出格式
如果小鸟可以无限使用这些设备，输出 $-1$ 。
否则输出小鸟在其中一个设备能量降为 $0$ 之前最多能使用多久。
（注意：设你的答案为 $a$ ，标准答案为 $b$ ，当 $a,b$ 有 $\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$ 的时候，你能得到本测试点的满分。)

分析
这题题述有些晦涩，但是实质仍然是二分板子。仍然是先抓条件表达式，即暴力穷举部分。首先理解题意，这些设备每个设备都拥有两个属性：每秒能量消耗量 $a_i$ 和初始能量 $b_i$ 。充电器可以每秒给接通的设备充能 $p$ 个单位。需要注意的是：可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。也就是说，每秒可以给任意多的设备充任意的能量，只需要保证充能之和小于 $p$ 即可。

转换一下思维，也就是说我们在任意的 $x$ 秒进行遍历，在设备耗能超过了原有能量的情况下，我们需要用充电器来充电，以补充这个差值，记这个差值为 $\Delta x$ 。而充电器在这 $x$ 秒内产生的电为 $px$ 个单位，如果 $px >\Delta x$ ，那么在 $x$ 秒时，保证所有设备能量均不降为0。

根据贪心的思想，在 $x$ 秒时，保证所有设备能量均不降为0，为局部解，又因为局部 = 最优，那么在 $x$ 秒内，保证所有设备能量均不降为0，满足题意，下面对该假设证明：

设在 $x$ 秒时，第 $i$ 个设备的能量为 $E_i(x)$ 。由于我们知道在 $x$ 秒时所有设备的能量都不低于0，即 $E_i(x) \geq 0$ 对于所有 $i = 1, 2, ..., n$ 成立。
考虑到从 $x-1$ 秒到 $x$ 秒这一秒钟内，第 $i$ 个设备的能量变化为：
$E_i(x) = E_i(x-1) - a_i + p_i$ 其中， $a_i$ 是第 $i$ 个设备每秒消耗的能量， $p_i$ 是这1秒内充电器给第 $i$ 个设备提供的能量（ $0 \leq p_i \leq p$ ）。既然 $E_i(x) \geq 0$ ，我们可以反推出 $E_i(x-1)$ 的值： $E_i(x-1) = E_i(x) + a_i - p_i$ 因为 $E_i(x) \geq 0$ 并且 $a_i > 0$ ，所以 $E_i(x-1) \geq 0$ 当且仅当 $p_i \leq a_i$ 。但即使 $p_i < a_i$ ，由于 $E_i(x) \geq 0$ ，加上 $a_i - p_i$ 后， $E_i(x-1)$ 仍然非负。此外，由于 $p_i$ 是充电器能够提供的能量，它不会超过 $a_i$ ，否则 $E_i(x)$ 将会小于0，与前提矛盾。
由数学归纳法，对于所有 $i$ ，我们有 $E_i(x-1) \geq 0$ ，即那么在 $x$ 秒内，保证所有设备能量均不降为0。

当然我们也可以不加证明地从主观上认为此贪心思路正确（事实上我们做贪心题更多的时候是靠直觉。那么条件的思路就很明确了，我们对时间进行二分，对于每一个二分得到的答案 $x$ ，我们把设备做成一个结构体，该结构体包含 $a_i$ 和 $b_i$ 两个变量。之后，我们只需比较总消耗能量sum $=\sum\limits_{i=0}^{n-1} a_i-xb_i$ 与充电器提供的总能量ep $=px$ ，如果 $ep \geq sum$ ，那么说明还可以用更长时间，此时取等进行贪心试探，右移左指针；如果 $ep < sum$ ，那么说明充电器已经超载了，只能用更少的时间，左移右指针。最后打印输出非试探的右指针。

同时，注意可以一直使用时的特判。输出 $-1.0000$ 。接下来你会迫不及待地将思路套进板子里然后提交。然后...

稻花香里说丰年，听取红黑一片

选取这道题的另外一个重要原因是这题是在实数域 $R$ 上进行二分，首先，我们的指针应该换用double类型，题中给出的表达式

\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}

告诉我们误差应该小于

10^{-4}

，也就是说，pv_r - pv_l

<10^{-4}

。这里不取等是因为后面的pv_l = mid + 1;要换成pv_l = mid，原因很简单，因为实数域的最小单位不是1，我们就不要这样来写了。同理pv_r = mid - 1要改成pv_r = mid，这样就是实数域下二分的板子。再次把思路写入板子中即可得到正确答案：

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

struct equip
{
    double ai;
    double bi;
}arr[100001];

int main()
{
    double n, p, sum = 0;
    cin >> n >> p;

    for (int i = 0; i < n; ++i) 
    {
        cin >> arr[i].ai >> arr[i].bi;
        sum += arr[i].ai;
    }

    if (p >= sum)
    {
        cout << -1.00000 << endl;
        return 0;
    }

    double pv_l = 0, pv_r = 1e10;

    while (pv_r - pv_l > 1e-4)
    {
        sum = 0;
        auto mid = (pv_r + pv_l) / 2;

        for (int i = 0; i < n; ++i)
        {
            if (arr[i].ai * mid <= arr[i].bi)
                continue;
            sum += abs(arr[i].ai * mid - arr[i].bi);
        }

        if (sum <= mid * p)
            pv_l = mid;
        else
            pv_r = mid;
    }

    cout << pv_r << endl;

    return 0;
}

D. 一元三次方程求解（普及-）

题目描述
有形如： $a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（其中 $a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$ 。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
提示：根的存在定理—记方程 $f(x) = 0$ ，若存在 $2$ 个数 $x_1$ 和 $x_2$ ，且 $x_1 < x_2$ ， $f(x_1) \times f(x_2) < 0$ ，则在 $(x_1, x_2)$ 之间一定有一个根。

输入格式
一行， $4$ 个实数 $a, b, c, d$ 。

输出格式
一行， $3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

分析
最返璞归真的一集（）选这个题的原因一方面是为了温习刚刚的实数域二分，另一方面就是活跃思维，遇到这中题直接拿着根去套板子是套不出来的，因为我们需要的是 $f(pv_l)f(pv_r)$ 的乘积小于0。但是这个题告诉了你根与根之差的绝对值 $\ge 1$ 。还是想找暴力，从 $-100.00扫到100.00$ ，根据二分可以先扫 $f(pv_l)$ 和 $f(pv_l + 1)$ ，然后再在这个区间里面再二分：

#include<cstdio>
#include<algorithm>

using namespace std;
double a, b, c, d;
double f(double x)
{
    return (x * x * x * a + x * x * b + x * c + d);
}
int main()
{
    double x1, x2, xx;
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
    for (double i = -100; i <= 100; i++)
    {
        x1 = i; x2 = i + 1;
        if (f(x1) == 0)
            printf("%.2lf ", i);
        if (f(x1) * f(x2) < 0)
        {
            while (x2 - x1 >= 0.001)
            {
                xx = (x1 + x2) / 2;
                if (f(x1) * f(xx) <= 0)
                    x2 = xx;
                else
                    x1 = xx;
            }
            printf("%.2lf ", x1);
        }
    }
}