P2678 [NOIP 2015 提高组] 跳石头

· · 算法·理论

题意：

共有n块石头，至多移走m块石头

问：最短跳跃距离的最大值

思路：

使用二分计算出mid，将mid当最短跳跃距离的最大值，判断需要挪走的石头的数量

若挪走的石头的数量大于m，则mid需要变小； 否则mid需要变大

而在check中，我们只需要判断区间，使区间[l,r]中a_r-a_l\le mid当达到极限时将l+1\sim r-1全部移走，并记录数量

程序：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn(1e6+10);
ll k,n,m;
ll a[maxn];
bool check(ll x){
    ll sum(0),id(0);
    for(ll i(1);i<=n;i++){
        if(a[i]-a[id]<x){
            sum++;
        }else{
            id=i;
        }
    }
    if(k-a[id]<x){
        sum++;
    }
    return m>=sum;
}
int main(){
    cin>>k>>n>>m;
    a[n+1]=k;
    for(ll i(1);i<=n;i++){
        cin>>a[i];
    }
    ll l(1),r(k);
    while(l<=r){
        ll mid((l+r)/2);
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<r<<'\n';
    return 0;
}