题解 P2678 【跳石头】

· · 题解

传送门

先感谢一下@ShawnZhou 大佬~

1. 题目简述

题目已经讲得很清楚了，形式化地说，你需要移走 N 块岩石中的 M 块，使得岩石之间的最小距离最远。

2. 思路分析

理解题意之后，我们来思考如何解决。

首先，我们可以肯定这道题使用枚举（因为无法直接求解）。

那么接下来有两种可能：

当我们枚举岩石时，我们的复杂度是 O(N^M) 的，显然会超时。

所以，我们只能枚举距离。当然，我们也不能把所有的距离都枚举一遍（这也太慢了）。所以，接下来要推出我们的二分了（这本身就是半道板子题好吗）。

3. 介绍二分

二分并不是在所有情况下都是可用的，使用二分需要满足两个条件：

这二者缺一不可。

有界

二分答案应该是在一个闭区间上进行的。用人话说，二分答案的答案是确定的，而不会出现多解。所以，二分一般用来解决最优解问题。

单调

举个栗子：我们小时候玩猜数字，范围从 1 到 100 （每次猜一个数，告诉你猜大了还是小了）。那么除了极个别欧皇之外，绝大部分人都会先猜 50 ，猜大了再猜 25，再猜小了猜 27，以此类推。

Bingo！这就是二分。那它满足什么呢？ ××××××√√√√√√ 单调
√√√√√√×××××× 单调
√×√√××√√√××√ 不单调

是不是还比较直观？

知道了二分符合什么条件，而题目又符合（出现了“最小值最大”就满足），那么就可以用二分求最优解。

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

那就好办了。我们二分距离，然后把这个距离“认为”是最短的跳跃距离，然后去检查是否可行。

4. 正确答案

（如果依旧看不懂可以看注释）

# include <bits/stdc++.h>
#define int long long
using namespace std;

int l, n, m, d[50005];

bool check (int dist)//检查函数 
{
    int tot = 0, place = 0, now = 0;
    //tot 是要为了满足 dist 的距离搬走的石头数量 
    //place 是上一块石头（因为中间有的石头可能已经被移走了） 
    //now 是现在正在检查那块石头 
    while (place <= n)
    {
        place ++;
        if (d[place] - d[now] < dist)   tot ++;//如果不符合要求，移走 
        else    now = place;//否则看下一个 
    }
    if (tot <= m)   return true;
    else    return false;
    //检查是否符合要求 
}

int calc () //二分的函数，姑且认为是半个板子 
{
    int a = 1, b = l, ans = -1;
    while (a <= b) 
    {
        int mid = (a + b) / 2;//取中间值（就像上文例子中第一次猜 50） 
        if (check (mid)) //如果符合要求 
        {
            ans = max (ans, mid);
            a = mid + 1;
            //去看是否有更优解 
        }
        else    b = mid - 1;
        //否则 mid - b 都不符合要求，缩小范围至 a - mid - 1 
    }
    return ans;
}

signed main()
{
    cin >> l >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> d[i];
    //以上是输入 
    d[n + 1] = l;
    //不要忘了终点的石头（所以共有 N + 1 块石头，当然，最后一块不能移） 
    cout << calc ();
    return 0; 
}