题解：P2678 [NOIP2015 提高组] 跳石头

wanghonghui123 · 2024-12-31 17:55:53 · 题解

思路

一道二分题，此题的关键是一个 check 函数。

关键点（check）

• 先遍历所有岩石，如果当前岩石和上一块每一掉岩石的的距离小于 mid（mid 是当前猜测的最小步数），就要移掉当前岩石，否则就要更新上一块未被一走的岩石的位置（也就是把上一块的位置是加 1）

• 判断要移走的是否不超过最多可以移掉的岩石数量。

时间复杂度为 \mathcal{O(n \log t)}，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N];
int t,n,m;
bool check(int mid){
    int cnt=0,l=0;
    for(int i=1;i<=n+1;i++){
        if(a[i]-a[l]<mid) cnt++;
        else l=i;
    }
    return cnt<=m;
}
int main(){
    cin>>t>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[n+1]=t;
    int l=0,r=t;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}