思路
两次二分，第一次二分最短的跳跃距离，第二次二分答案最短跳跃距离的最大值，两个值显然具有单调性并且题目保证不会出现两个一样的。但仔细思考之后可以只要一次二分+贪心的check就可以了。如果最短距离设为 x可行 \(移走 <= M 块\) ，那么设为比 x小的值一定也可行显然有单调性二分即可，贪心思路就是从左到右扫描，尽量保留石头，只移走那些导致跳跃距离不够的石头。两次二分时间复杂度显然 \(\Theta(n \log L)\) 而贪心的时间复杂度为 \(\Theta(n \log L)\) 但是两次二分常数显然更大。
实现
check大概就是这个样子，从左到右扫描，尽量保留石头，只移走那些导致跳跃距离不够的石头。
auto ok = [&](ll X) -> bool {ll removed=0; ll prev=0; for (ll i=0;i<n;i++) {if (Dist[i] - prev < X) {removed++;} else {prev = Dist[i];}}if (l - prev < X) {if (removed < m) {removed++; } else {return false; }}return removed <= m;};
AClink。
ACcode
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define i128 __int128
#define ld long double
#define fir first
#define sec second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
const int MOD=998244353;
const int MOD1=1e9+7;
//char ibuf[1<<25],*p1=buf,*p2=buf;
mt19937 mrand(random_device{}());
int rnd(int x){ return mrand() % x;}
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;}
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}
//C++ 17 -O2
//By MaZhaoze
int main(){ios::sync_with_stdio(0);cin.tie(0);ll l,n,m;cin>>l>>n>>m;vector<ll> Dist(n);for(auto &x:Dist) cin>>x;// sort(Dist.begin(),Dist.end());auto ok = [&](ll X) -> bool {ll removed=0; ll prev=0; for (ll i=0;i<n;i++) {if (Dist[i] - prev < X) {removed++;} else {prev = Dist[i];}}if (l - prev < X) {if (removed < m) {removed++; } else {return false; }}return removed <= m;};ll L=1,r=1e9+7,ans=0;while(L<=r){ll mid=(L+r)/2;if(ok(mid)){ans=mid;L=mid+1;}else{r=mid-1;}}cout<<ans;return 0;
}