O(nL)

从大到小去枚举所有点，判断是否可以跳到终点。第一次可以跳到的就是最短距离的最大值.

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int a[N];
int L,n,m;
bool check(int mid)
{
    int last=0,cnt=0; //上一个石头的位置和移走的石头数目 
    for(int i=1;i<=n;i++)
    {
        if(a[i]-last>=mid) last=a[i]; //更新上一个石头的距离 
        else cnt++; //移走 
    }
    return cnt<=m; //说明距离可以更大 
}
int main()
{
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    n++;
    a[n]=L;
    int l=0,r=L;
    for(int i=r;i>=1;i--)
    {
        if(check(i)) //最短距离为i的时候,可以跳到终点
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}

$nlgL$

容易知道跳跃距离可以二分。

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int a[N];
int L,n,m;
bool check(int mid)
{
    int last=0,cnt=0; //上一个石头的位置和移走的石头数目 
    for(int i=1;i<=n;i++)
    {
        if(a[i]-last>=mid) last=a[i]; //更新上一个石头的距离 
        else cnt++; //移走 
    }
    return cnt<=m; //说明距离可以更大 
}
int main()
{
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    n++;
    a[n]=L;
    int l=0,r=1e9;
    while(l<r) //枚举当前跳跃的最短距离
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid; //当前长度可以 
        else r=mid-1;
    }
    cout<<l;
    return 0;
}