营销型网站要点,没有经验可以做网站编辑吗,免费下载app软件官网,怎样建设自己的物流信息网站1、题目 二、题解#xff1a; 2.1解题思路:
1.题目要求求出最小值最大#xff0c;明显的二分答案题目#xff0c;所以我们可以二分可以跳跃距离int l-1,rL1;
2.此时我们思考lmid和rmid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的#xff0c;
那么…1、题目 二、题解 2.1解题思路:
1.题目要求求出最小值最大明显的二分答案题目所以我们可以二分可以跳跃距离int l-1,rL1;
2.此时我们思考lmid和rmid的处理,当我们的check(mid)为true时候 表明我们此时的mid是符合要求的
那么我们就要考虑是否可以变得更大呢因此我们的二分答案可以这样写int l-1,rL1;while(l1r){int mid(lr)1;if(check(mid)) lmid; //当check为true时表示符合条件我们就要考虑是否可以更大else rmid;} if(check(r)) coutr\n;else coutl\n;3.接下来我们来处理check(mid)函数
法一好实现但是难想
首先我们定义一些变量来处理问题
int cnt0; //计数器
int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上接下来我们枚举每一个石头
1.并且我们无论如何都会往下枚举所以i是永恒成立的
2.那么问题来了我们如何实现把一个石头给踢掉的操作呢2.1.答案是通过操作cnt和now因为当需要踢掉这个石头的时候一定需要1的所以cnt;
但是我们此时不一定可以让nowi因为我们可能会出现需要搬走连续的两个石头所以只有当
a[i]-a[now]mid我们才会跳跃代码解析
bool check(int mid) //检查此时这个距离是否可以达成
{int cnt0; //计数器int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上while(in1) //枚举每一个石头{i;if(a[i]-a[now]mid) //表明此时的距离不满足要求{cnt; //纯让次数加1,也就是当作把这块石头踢掉因为我此时i是必然会进行的//但是我的now没有改变也就意味着这块石头我没有跳遍历到了下一块石头。}else //表明此时距离已经mid可以跳跃{nowi; //}}if(cntm) return true;else return false;
}法二(好想但是难实现)
首先我们定义一些变量来处理问题
int cnt0; //计数器
int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上接下来我们枚举每一个石头
1.并且我们无论如何都会往下枚举所以i是永恒成立的
2.那么问题来了我们如何实现把一个石头给踢掉的操作呢2.1:在法一中我们通过cnt的处理来抽象的实现跳跃这个操作
但是我们仍然可以用一个whle死循环来实现两个/两个以上的连续石头不符合条件的情况我们把if–while这样当出循环时就一定使得此时的下一个石头的距离是合理的。 PS:注意此时需要防止i的遍历溢出 代码如下:
bool check(int mid) //检查此时这个距离是否可以达成
{int cnt0; //计数器int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上while(in1) //枚举每一个石头{i;while(a[i]-a[now]mid) //表明此时的距离不满足要求{cnt;if(in1) //还没遍历完成{i; //防止都不满足溢出}else //表明此时i已经遍历完了n,那么就直接进行判断{if(cntm) return true;else return false;}}nowi; //表示跳到这个石头上面}if(cntm) return true;else return false;
}三、完整代码解析
法一
#includeiostream
using namespace std;const int N2e5;
int a[N];
int L,n,m;bool check(int mid) //检查此时这个距离是否可以达成
{int cnt0; //计数器int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上while(in1) //枚举每一个石头{i;if(a[i]-a[now]mid) //表明此时的距离不满足要求{cnt; //纯让次数加1,也就是当作把这块石头踢掉因为我此时i是必然会进行的//但是我的now没有改变也就意味着这块石头我没有跳遍历到了下一块石头。}else //表明此时距离已经mid可以跳跃{nowi; //}}if(cntm) return true; //踢石头数可以踢的数量 满足条件else return false;
}int main()
{cinLnm;for(int i1;in;i){cina[i];}a[n1]L; //样例准备int l-1,rL1;while(l1r){int mid(lr)1;if(check(mid)) lmid;else rmid;}if(check(r)) coutr\n;else coutl\n;return 0;
}法二
#includeiostream
using namespace std;const int N2e5;
int a[N];
int L,n,m;bool check(int mid) //检查此时这个距离是否可以达成
{int cnt0; //计数器int i0,now0; //i--枚举每一个石头,now表示当前跳到了哪一个石头上while(in1) //枚举每一个石头{i;while(a[i]-a[now]mid) //表明此时的距离不满足要求{cnt;if(in1) //还没遍历完成{i; //防止都不满足溢出}else //表明此时i已经遍历完了n,那么就直接进行判断{if(cntm) return true;else return false;}}nowi; //表示跳到这个石头上面}if(cntm) return true;else return false;
}int main()
{cinLnm;for(int i1;in;i){cina[i];}a[n1]L; //样例准备int l-1,rL1;while(l1r){int mid(lr)1;if(check(mid)) lmid;else rmid;}if(check(r)) coutr\n;else coutl\n;return 0;
}
