题目传送门

思路

不难发现答案具有单调性。若最短跳跃距离的最大值为 $X$，那么对于 $X-1$ 以及所有 $<X$ 的数，选手一定能跳过去。反之如果它 $>X$，则一定超过了 $M$，不可行。考虑二分。

二分最短跳跃距离。对于每一次尝试的距离 $X$，每次以起点向前遍历找到第一个 $<X$ 的点，增加答案次数，并跳跃至当前点。最后判断答案次数是否 $\le M$ 即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e4+10;
int n,m,a[N];
bool check(int x){
	int cnt=0,p=0;
	for(int i=1;i<=n+1;++i)
		if(a[i]-a[p]<x)
			++cnt;
		else p=i;
	return cnt<=m;
}
int main(){
	int lrd=read();
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	a[n+1]=lrd;
	int l=1,r=1e9;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))
			l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
	return 0;
}

#include <bits/stdc++.h> 
using namespace std;
const int N=51100;
int n, m, L, a[N], b[N];
bool check(int x)
{
    int s=0, tm=1;
    for(int i=1;i<=n;i++)
    {
        s = s + b[i];
        if(s >= x)
        {
            tm++; if(tm > m) return 1;
            s = 0;
        } 
    }
    return tm > m;
}
int main()
{
    scanf("%d%d%d", &L, &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    a[0] = 0; a[++n] = L;
    sort(a+1, a+n+1);
    for(int i=1;i<=n;i++) b[i] = a[i] - a[i-1];
    int l=0, r=L, ans;  m = n - m; // 问题转化为有n条线段长度为b[i]，能否组装m段，每段长度至少为x 
    while(l <= r)
    {
        int mid = (l + r)/2;
        if(check(mid)) l = mid + 1,ans = mid;
        else r = mid - 1;        
    }
    printf("%d", ans);
    return 0;
}