算法题（144）：跳石头

审题：
本题需要我们找出移动次数小于等于m的最大最短跳跃距离

思路：

方法一：二分答案

由于本题出现了最大最短跳跃距离这个最大最小值的关键词，我们考虑对答案区间（跳跃距离）使用二分查找

跳跃距离越大，移动次数越多，所以跳跃距离和移动次数呈正相关

移动策略：

若cnt小于等于m：left = mid

若cnt大于m:right = mid -1

mid计算策略：

mid = (left+right+1)/2

移动次数计算：

当上一个保留的石头与后面遍历到的石头之间的距离小于num的时候，我们可以将当前遍历到的石头移除

当我们遍历到n+1位置，也就是终点位置的时候：

若上一个保留的石头和终点之间的距离也小于num，说明最后一段距离不够，我们需要从当前保留的最后一个石头开始移除至少一个前面保留过的石头才能保证最短距离大于等于num。但是只要出现了最后一段距离不够，cnt++后一定大于m

• 终点距离不足意味着：无论如何移除前面的岩石，最后一段距离都无法满足 ≥ num

• 如果 cnt++ 后 ≤ m，说明还可以继续移除岩石来尝试满足条件，这与"终点距离不足"矛盾

P2678 [NOIP 2015 提高组] 跳石头 - 洛谷

解题：

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
ll l, n, m;
ll a[N]; // 改为ll类型避免溢出ll calcnt(ll num)
{ll cnt = 0;ll last_pos = 0; // 起点位置0for (int i = 1; i <= n + 1; i++) // 包含终点{if (a[i] - last_pos < num){cnt++;}else{last_pos = a[i];}}return cnt;
}int main()
{cin >> l >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}a[n + 1] = l; // 添加终点ll left = 1, right = l;while (left < right){ll mid = (left + right + 1) / 2;if (calcnt(mid) <= m){left = mid;}else{right = mid - 1;}}cout << left << endl;return 0;
}