P2678 【跳石头】

有朋自远方来 · 2019-11-01 19:24:36 · 题解

题解.

一. 题目分析

我们可以看到 最短跳跃距离尽可能长 , 所以这题肯定是二分做法了.

那么二分什么呢？很显然可以看出就是 最短跳跃距离.

二. 二分检测

Check 函数.设二分最短跳跃距离为 Mid.

我们考虑到了 i 和 i+1 两块石头.

• 如果这两块石头之间距离大于等于 Mid,那么可以跳过（跳跃距离满足条件）.

• 否则，我们应该移走第 i 块石头，使得两块石头之间距离大于等于 Mid.

最后，我们看移走的石头个数是否小于等于 M 即可.

二分边界： l=0,r=L.

三. 代码

#include<iostream> 

using namespace std;

long long L,N,M,d[50005],ans;

bool check(long long mid)
{
    int temp=0,now=0;
    for(int i=1;i<=N;i++)
        if(d[i]-d[now]<mid)  temp++;//移走这块石头
        else now=i;//不移走
    if(temp>M)  return false;
    return true;//能更新答案
}

int main()
{
    cin>>L>>N>>M;//读入
    for(int i=1;i<=N;i++)  cin>>d[i]; 

    int l=0,r=L;//二分
    while(l<=r)
    {
        long long mid=(l+r)>>1;
        if(check(mid))  ans=mid,l=mid+1;
        else r=mid-1;
    }

    cout<<ans<<endl;//输出

    return 0;
}