A49 跳石头 题解

Solution

---

首先看题目：求最长的最短跳跃距离。
看到“最长的最短”和“最短的最长”就可以直接确定是二分答案。

二分的板子肯定都会：

int l=1,r=L;
while(l<r){
    int mid=(l+r+1)/2; // +1 向上取整
    if(check(mid)) l=mid;
    else r=mid-1;
}
printf("%d",l);

接下来考虑 check() 函数怎么写（二分答案最重要的部分）。

我们二分枚举的是最长的最短跳跃距离（也就是 mid）。

对于每个 mid，当下一块石头与当前石头的距离小于 mid 时就不满足最短跳跃距离，此时就需要移走一块石头。

否则就可以跳，跳过去之后更新现在站的石头的位置。

bool check(int mid){
    int cnt=0,last=0; // last 为现在站的石头的位置
    for(int i=1;i<=n;i++){
        if(dis[i] - last < mid){ // 不满足 “mid 是最短跳跃距离”
            cnt++; // 需要移走石头
        }else{
            last = dis[i]; // 跳过去，更新现在站的位置
        }
    }
    if(L-last < mid) cnt++; // 还没有到终点，但是不满足条件，所以需要移走石头
    return cnt <= m; // 返回 “最多移走 m 个石头” 是否成立
}

核心部分讲完，现在给出完整代码。

AC Code

#include <iostream>
using namespace std;
const int N = 5e4+2;
int L,n,m;
int dis[N];
bool check(int mid){
    int cnt=0,last=0;
    for(int i=1;i<=n;i++){
        if(dis[i] - last < mid){
            cnt++;
        }else{
            last = dis[i];
        }
    }
    if(L-last < mid) cnt++;
    return cnt <= m;
}
int main(){
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>dis[i];
    }

    int l=1,r=1e9;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}

$\texttt{Lu}\operatorname{ogu}$ 最优解：https://www.luogu.com.cn/record/294580840 $\color{lightgreen} \fbox{43ms}$ 欢迎超越