P2678 [NOIP 2015 提高组] 跳石头——题解

解题思路

二分最短距离 $d$。从起点开始扫描岩石，如果当前岩石与上一块保留岩石的距离小于 $d$，就必须移走当前岩石；否则保留并更新位置。若所需移除数量不超过 $M$，则 $d$ 可行。

复杂度分析

每次检查 $O(N)$，总时间 $O(N\log L)$，空间 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int L,N,M;cin>>L>>N>>M;vector<int>a(N+2);a[0]=0;for(int i=1;i<=N;i++)cin>>a[i];a[N+1]=L;
    auto ok=[&](int d){int del=0,last=0;for(int i=1;i<=N+1;i++){if(a[i]-a[last]<d)del++;else last=i;}return del<=M;};
    int lo=0,hi=L,ans=0;while(lo<=hi){int mid=(lo+hi)/2;if(ok(mid))ans=mid,lo=mid+1;else hi=mid-1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int L,N,M;cin>>L>>N>>M;vectora(N+2);a[0]=0;for(int i=1;i<=N;i++)cin>>a[i];a[N+1]=L; auto ok=[&](int d){int del=0,last=0;for(int i=1;i<=N+1;i++){if(a[i]-a[last]<d)del++;else last=i;}return del<=M;}; int lo=0,hi=L,ans=0;while(lo<=hi){int mid=(lo+hi)/2;if(ok(mid))ans=mid,lo=mid+1;else hi=mid-1;} cout<<ans<<'\n';return 0; }