算法日记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;
}