二分：
所求解的为在恶魔破坏不超过 $M$ 片荷叶时，最短跳跃距离的最大值，此时我们可以二分该最大值。
设当前跳跃距离为 $x$，在判定过程中，该距离是否合法，即在破坏小于等于 $M$ 片荷叶时的最短跳跃距离能否达到 $x$，如果能达到，则距离还可更大即 $l = x$（恶魔还能破坏），否则该距离无法达到 $r = x - 1$（恶魔不可破坏），不断二分则可得到最优解。
注意：
判定过程，可统计可选的点即相邻点大于等于 $x$ 的点的数目，与 $M$ 进行比较即可。
#include <iostream> using namespace std; const int N = 50010; int L, n, m; int a[N]; bool check(int dist) { int cnt = 0; int last = 0; for (int i = 0; i < n; ++i) { if (a[i] - last >= dist) cnt++, last = a[i]; // 统计可行点的个数，不可行则被剔除 } return cnt >= n - m; } int main() { cin >> L >> n >> m; for (int i = 0; i < n; ++i) cin >> a[i]; int l = 0, r = L; while (l < r) { // 二分最短跳跃距离的最大值 int mid = l + r + 1 >> 1; if (check(mid)) l = mid; // 距离可以更大，因为恶魔还可损坏 else r = mid - 1; // 距离过大，因为恶魔已超过自身能够损坏的数目 } cout << l << endl; return 0; }
原文：https://www.cnblogs.com/xuwenchao/p/14584133.html