题解：P10909 [蓝桥杯 2024 国 B] 立定跳远

· · 题解

P10909（二分）

思路分析：

首先观察到本题答案具有单调性，于是我们可以考虑二分最远距离 L。

然后考虑如何检查答案，对于原有的这些检查点，每两个检查点之间需要 \lceil \frac{dis}{L} \rceil-1 个新增检查点，其中 dis 表示两个检查点之间的距离，然后判断总检查点个数是否小于 m 就可以了。

那么爆发技能我们该怎么处理呢？由于使用技能可以使距离变成原来的两倍，其实就相当于新增了一个检查点，所以只用给 m 加一就可以了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,d[N];
bool check(int a){//检查是否合法
    int cnt=0;
    for(int i=1;i<=n;i++)
        cnt+=int(double(d[i]-d[i-1])/double(a)+0.999999)-1;
    return cnt<=m+1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    int l=1,r=d[n],mid;
    while(l<r){//二分答案
        mid=l+r>>1;
        if(check(mid))  r=mid;
        else  l=mid+1;
    }
    printf("%d",l);
    return 0;
}