洛谷P2678 跳石头 题解
题目概述
在一条长度为L的笔直河道中，起点在0位置，终点在L位置。起点和终点之间有 N 块岩石，每块岩石的位置已知且按升序给出。
现在，你可以移走最多M块岩石（不能移走起点和终点的岩石），目标是让选手在跳跃过程中，所有相邻岩石之间的最短跳跃距离尽可能大。你需要输出这个最大的最短跳跃距离。
分析
暴力模拟会非常耗时，显然行不通。用直接模拟也十分困难。但是我们发现，这是一个典型的最小值最大问题，而且答案具有一定的范围（\([1,l]\)），可以尝试去二分答案，看看答案是否单调：我们发现，如果通过移走\(\le\)M块石头满足了一个最短跳跃距离，那么一定可以通过某种方案满足任意的比它更小的最短跳跃距离，反之，如果一个最短跳跃距离无法实现，那么比他跟大的也一定无法实现。
所以，我们可以通过二分去找到最大的可行值。记某一猜测值为res，核心在与怎么判断res是可行的，也就是check函数。我们知道，移走一块与它前面一块岩石的距离本就比res大的岩石，结果是不会变的，也就是说，我们需要处理那些原先与前一块岩石的距离就比res短的,把它移走，才能满足条件，同时，在搬走所有有影响的岩石后，我们还有注意有一个M限定着，所以如果最后总共搬走的石头数量超过了限制的M，就可以确定res是一个不可行值。
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e4 + 5;
int l, n, m;
int dist[N];bool check(int x)
{int cnt = 0; // 记录完成目标需要移走的石头数量int last = 0; // 上一个要保留的石头距起点的位置，初始为起点for (int i = 1; i <= n + 1; i++){if (dist[i] - last < x) // 小于目标，不满足，需要移走这块石头{cnt++;}else{last = dist[i]; // 保留这块石头，更新last}}return cnt <= m;
}int main()
{cin >> l >> n >> m;dist[0] = 0;dist[n + 1] = l;for (int i = 1; i <= n; i++){cin >> dist[i];}// 二分答案int left = 1, right = l + 1;while (left + 1 < right){int mid = (left + right) >> 1;if (check(mid)){left = mid;}else{right = mid;}}cout << left << endl;
}
总结
看到最大的最小值或者最小的最大值，一般是二分答案