算法日记1：洛谷p2678跳石头(二分答案)

1、题目

二、题解：

2.1解题思路:

1.题目要求求出最小值最大，明显的二分答案题目，所以我们可以二分可以跳跃距离

int l=-1,r=L+1;

2.此时我们思考l=mid和r=mid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的，
那么我们就要考虑是否可以变得更大呢？因此我们的二分答案可以这样写

    int l=-1,r=L+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;	//当check为true时，表示符合条件，我们就要考虑是否可以更大
        else r=mid;
    } 
    if(check(r)) cout<<r<<'\n';
    else cout<<l<<'\n';

3.接下来，我们来处理check(mid)函数

法一：好实现但是难想

首先我们定义一些变量来处理问题
int cnt=0;  //计数器
int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上

接下来，我们枚举每一个石头，
1.并且我们无论如何都会往下枚举，所以i++是永恒成立的
2.那么问题来了，我们如何实现把一个石头给踢掉的操作呢？

2.1.答案是通过操作cnt和now，因为当需要踢掉这个石头的时候，一定需要+1的，所以cnt++;
但是我们此时不一定可以让now=i，因为我们可能会出现需要搬走连续的两个石头，所以只有当
a[i]-a[now]>mid，我们才会跳跃

代码解析

bool check(int mid) //检查此时这个距离是否可以达成
{
    int cnt=0;  //计数器
    int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
    
    while(i<n+1)    //枚举每一个石头
    {
        i++;
        if(a[i]-a[now]<mid)   //表明此时的距离不满足要求
        {
            cnt++;  //纯让次数加1,也就是当作把这块石头踢掉，因为我此时i++是必然会进行的，
                    //但是我的now没有改变也就意味着这块石头我没有跳，遍历到了下一块石头。
        }
        else    //表明此时距离已经>mid可以跳跃
        {
            now=i;  //
        }
    }
    if(cnt<=m) return true;
    else return false;
}

法二(好想但是难实现)：

首先我们定义一些变量来处理问题
int cnt=0;  //计数器
int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上

接下来，我们枚举每一个石头，
1.并且我们无论如何都会往下枚举，所以i++是永恒成立的
2.那么问题来了，我们如何实现把一个石头给踢掉的操作呢？

2.1:在法一中，我们通过cnt的处理来抽象的实现跳跃这个操作
但是我们仍然可以用一个whle死循环来实现两个/两个以上的连续石头不符合条件的情况

我们把if–>while，这样，当出循环时，就一定使得此时的下一个石头的距离是合理的。
PS:注意此时需要防止i的遍历溢出！！！
代码如下😂:

bool check(int mid) //检查此时这个距离是否可以达成
{
    int cnt=0;  //计数器
    int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
    
    while(i<n+1)    //枚举每一个石头
    {
        i++;
        while(a[i]-a[now]<mid)   //表明此时的距离不满足要求
        {
            cnt++;
            if(i<n+1)   //还没遍历完成
            {
                i++;    //防止都不满足溢出
            }
            else    //表明此时i已经遍历完了n,那么就直接进行判断
            {
                if(cnt<=m) return true;
                else return false;
            }
        }
        now=i;      //表示跳到这个石头上面
    }
    if(cnt<=m) return true;
    else return false;
}

三、完整代码解析

法一：

#include<iostream>
using namespace std;

const int N=2e5;
int a[N];
int L,n,m;

bool check(int mid) //检查此时这个距离是否可以达成
{
    int cnt=0;  //计数器
    int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
    
    while(i<n+1)    //枚举每一个石头
    {
        i++;
        if(a[i]-a[now]<mid)   //表明此时的距离不满足要求
        {
            cnt++;  //纯让次数加1,也就是当作把这块石头踢掉，因为我此时i++是必然会进行的，
                    //但是我的now没有改变也就意味着这块石头我没有跳，遍历到了下一块石头。
        }
        else    //表明此时距离已经>mid可以跳跃
        {
            now=i;  //
        }
    }
    if(cnt<=m) return true;	//（踢石头数<可以踢的数量）   满足条件
    else return false;
}



int main()
{
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1]=L;   //样例准备
    
    int l=-1,r=L+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    
    if(check(r)) cout<<r<<'\n';
    else cout<<l<<'\n';
    
	return 0;
}

法二：

#include<iostream>
using namespace std;

const int N=2e5;
int a[N];
int L,n,m;

bool check(int mid) //检查此时这个距离是否可以达成
{
    int cnt=0;  //计数器
    int i=0,now=0;  //i-->枚举每一个石头,now表示当前跳到了哪一个石头上
    
    while(i<n+1)    //枚举每一个石头
    {
        i++;
        while(a[i]-a[now]<mid)   //表明此时的距离不满足要求
        {
            cnt++;
            if(i<n+1)   //还没遍历完成
            {
                i++;    //防止都不满足溢出
            }
            else    //表明此时i已经遍历完了n,那么就直接进行判断
            {
                if(cnt<=m) return true;
                else return false;
            }
        }
        now=i;      //表示跳到这个石头上面
    }
    if(cnt<=m) return true;
    else return false;
}



int main()
{
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1]=L;   //样例准备
    
    int l=-1,r=L+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    
    if(check(r)) cout<<r<<'\n';
    else cout<<l<<'\n';
    
	return 0;
}