🎈 原创

洛谷 P2678 跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 NN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 MM 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 L,N,ML,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L \geq 1L≥1 且 N \geq M \geq 0N≥M≥0。

接下来 NN 行，每行一个整数，第 ii 行的整数 D_i( 0 < D_i < L)D**i(0<D**i<L)， 表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

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

输入输出样例

输入 #1

25 5 2 
2
11
14
17 
21

输出 #1

4

说明/提示

输入输出样例 1 说明：将与起点距离为 22和 1414 的两个岩石移走后,最短的跳跃距离为 44(从与起点距离 1717 的岩石跳到距离 2121 的岩石,或者从距离 2121 的岩石跳到终点)。

另：对于 20%20%的数据,0 ≤ M ≤ N ≤ 100≤M≤N≤10。

对于50%50%的数据,0 ≤ M ≤ N ≤ 1000≤M≤N≤100。

对于 100%100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,0000≤M≤N≤50,000,1≤L≤1,000,000,000。

---

分析

其实这道题一开始没看出怎么二分，看了题解才明白，真的是有点脑经急转弯的感觉了。

这道题二分的是最短的跳跃距离，左边界Left为1，因为题目说L最小为1，右边界Right为L，因为最短的跳跃距离大于这个值就没有意义了。

这是还需要一个judge函数，来判断此时的mid是否符合条件，来决定之后在那个区间里继续二分。这也是这道题最难想的地方，我也是看了题解才懂。judge函数的实现就是模拟这个跳石头的过程，对距离数组的dis[0]设为0，dis[N + 1] = L，分别表示起点和终点，然后从1到N + 1遍历这个距离数组，当当前的减去上一个的距离小于当前假设的最小距离时，就表示这块石头需要移除。

但是这里逻辑上有一点矛盾，就是当i为N + 1时，如果此时减去上一个的距离不符合条件时，说明当前这块石头要移去，但是题目上说起点和终点的石头是不能移走的。这里就需要理解为把终点的前一块移走，其实这里我有一点没想明白，但是这样做是符合题目条件的，最后的结果是正确的。（我好菜QAQ）

---

代码

#include <iostream>
#include <algorithm>
using namespace std;

long long L, N, M;
long long dis[50010];
bool judge(long long mid);

int main(int argc, const char * argv[])
{
    cin >> L >> N >> M;
    dis[0] = 0;
    for(int i = 1; i <= N; i++)
        cin >> dis[i];
    dis[N + 1] = L;

    long long Left = 1, Right = L;
    while(Left <= Right)
    {
        long long mid = (Left + Right) / 2;
        if(judge(mid))
            Left = mid + 1;
        else
            Right = mid - 1;
    }
    cout << Right << endl;


    return 0;
}

bool judge(long long mid)
{
    long long cnt = 0;
    int last = 0;
    for(int i = 1; i <= N + 1; i++)
    {
        if(dis[i] - dis[last] < mid)
            cnt++;
        else
            last = i;
    }
    if(cnt > M)
        return false;
    else
        return true;
}

其他

再附上一道差不多的
洛谷P1182数列分段

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, num[100010], MAX = -1;
bool judge(int mid);

int main(int argc, const char * argv[])
{
    cin >> N >> M;
    int L = 0, R = 0;
    for(int i = 0; i < N; i++)
    {
        cin >> num[i];
        if(num[i] > MAX)
            MAX = num[i];
        R += num[i];
    }
    L = MAX;
    while(L <= R)
    {
        int mid = (L + R) >> 1;
        if(judge(mid))
            R = mid - 1;
        else
            L = mid + 1;
    }
    cout << L << endl;


    return 0;
}


bool judge(int mid)
{
    int sum = 0, cnt = 0;
    for(int i = 0; i < N; i++)
    {
        if(sum + num[i] <= mid)
            sum += num[i];
        else
        {
            sum = num[i];
            cnt++;
        }
    }
    if(cnt < M)
        return true;
    else
        return false;
}

总结

对于这些题目，只要看到是要求最大值的最小，就要知道是要用二分。
因为相当于是找一个边界，一边都是符合条件的，另一边是不符合的，此时就要看清楚到底哪边才是符合条件的，最后到底是取L还是R。