P2678 题解

ikunTLE · 2024-12-29 00:00:07 · 题解

题目传送门

思路

不难发现答案具有单调性。若最短跳跃距离的最大值为 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;
}