小白的题解 小白的理解 全部Typora上写给自己粘贴过来的
描述
输出格式:
一个整数,即最短跳跃距离的最大值。
这里特地表明了一下这个输出格式 说实话 第一眼看上去是真的看不懂这个意思 又是最大又是最小 但是这个就是这道题目的算法的思路的关键 二分好像就是需要求 大于等于x 也就是最大值里面的等于的时候的最小值。。和小于等于x 也就是最小值里面的最大值。。还真的就很巧 这道题目要求的就是最小值里面的最大值 也就是小于等于x 那么check后面的二分边界就好弄了
C++ 代码
#include <iostream>
using namespace std;
int m, n, k;
const int N = 50010;
int q[N];
bool check(int mid)
{
int last = 0, cnt = 0; //长点心 这个cnt是定义在这边的~~不是定一个全局变量就好了。。
for(int i = 0; i <= n; i ++)
if(q[i] - last < mid) cnt ++; //这里很细节下面第一点说
else last = q[i];
return cnt <= m;
}
int main()
{
scanf("%d%d%d", &k, &n, &m);
for(int i = 0; i < n; i ++) cin >> q[i];
q[n] = k; //最后一个的边界需要放进去 不然最后还需要单特判
int l = 0, r = k; //左右边界
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid; //左边界是有原因的 下面第二点说
else r = mid - 1;
}
cout << r << endl;
return 0;
}
- 本人推到了很久 本人很累~ 主要是还是第一次的思想错了 导致后面走了错路 所以啊 第一次一定要做对 确定边界,首先是需要看上面的check函数返回true的时候的情况 在这里 首先是需要深刻的了解题目的意思的 说实在的 这道题目的思路是真的很绕 首先是一堆的石头 以及每一个石头到起点的距离 题目的意思是再跳的时候可能会搬掉m块石头 但是搬掉的石头是不确定的 就是搬掉这m块石头之后 最后计算一下两个石头之间的距离 寻找距离的最大值 也就是说搬掉哪m块石头之后距离的最小值最大。。。说实在的 很抽象。。不好理解,那么一段代码的意思就是 遍历每一块儿石头 算出他和她前面没有被搬掉的石头的距离 注意这里是没有被搬掉的石头,如果前面的石头被搬掉了呢 所以这边需要在石头搬掉之后在遍历到下一块石头的时候将下一块不需要搬掉的石头设置为下面需要便利的石头需要作比较的石头 当作差之后小于mid的话说明这个石头是可以搬掉的 因为它在last到mid的范围之内 按照mid的长度跳一次这块石头就不会被踩到 所以可以搬掉 最后计算所有的搬掉的石头cnt 如果这个值小于等于m的话 说明当前mid的值小了 小的基本所有的石头都忽略不了那么就把mid增加 所以check时需要 l = mid 或者也可以换一种思路,当前需要找的是满足条件的最大值 对应q[mid] <= x 所以后面 l = mid
- 对于2,,参见1.。。。。。。。。。。。。。。。。。
写挺好,给你个赞👍