[蓝桥杯C++ 2024 国 B ] 立定跳远(二分)

题目描述

在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1,a_2,\cdots ,a_n$ 且 $a_i\ge a_{i-1}>0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时，小明可以自行再增加 $m$ 个检查点让自己跳得更轻松。

在运动会前，小明制定训练计划让自己单次跳跃的最远距离达到 $L$，并且学会一个爆发技能可以在运动会时使用一次，使用时可以在该次跳跃时的最远距离变为 $2L$。小明想知道，$L$ 的最小值是多少可以完成这个项目？

输入格式

输入共 $2$ 行。

第一行为两个正整数 $n,m$。

第二行为 $n$ 个由空格分开的正整数 $a_1,a_2,\cdots ,a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

5 3
1 3 5 16 21

输出 #1

3

说明/提示

【样例说明】

增加检查点 $10,13,19$，因此每次跳跃距离为 $1,2,2,5,3,3,3,2$，在第三次跳跃时使用技能即可。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $n\le 10^2$，$m\le 10^3$，$a_i\le 10^3$。
对于 $100\%$ 的评测用例，保证 $2\le n\le 10^5$，$m\le 10^8$，$0<a_i\le 10^8$。

解题核心思路是通过二分查找来确定小明单次跳跃的最小距离 L，同时考虑到他可以使用一次爆发技能将某一次跳跃距离变为 2L
对于每个候选的 L（即 mid），计算在不使用技能的情况下，需要添加多少个新检查点才能使所有跳跃距离不超过 L。
具体计算方法：对于每两个相邻的原检查点 a[i-1] 和 a[i]，所需的新检查点数为 ceil((a[i] - a[i-1]) / mid) - 1。
如果总添加的检查点数不超过 m + 1，则说明当前 L 可能是可行的（因为可以用一次技能覆盖一个较长的跳跃）。
关键逻辑：通过允许添加 m + 1 个检查点（而不是 m 个），我们隐式地利用了一次技能的机会，因为技能可以将一次跳跃距离翻倍，相当于减少了一个需要添加检查点的间隔。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],ans;

bool check(int mid){
    int cnt=0;
    for(int i=1;i<=n;++i){
        cnt+=(int)ceil((a[i]-a[i-1])*1.0/mid)-1;
    }
    return cnt<=m+1;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    int l=1,r=a[n];
    while(l<r){
        int mid=l+r>> 1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}