🧠 解题思路
这个问题是一个经典的 二分答案 + 贪心验证 问题。
1️⃣ 思考目标
我们希望 最大化最小安全距离，记为 x。
那么问题变为：
给定最小安全距离 x，能否通过清理 ≤ M 块残骸使得所有连续航段距离都 ≥ x？
如果可以，说明 x 是可行的；否则不可行。
于是可以用二分搜索 x 的最大可行值。
2️⃣ 贪心验证函数 check(x)
思路：
- 从起点开始遍历残骸；
- 记录上一个“保留的残骸”位置；
- 若当前残骸距离上一个保留点 <
x，则清理掉该残骸； - 否则保留它。
最后统计清理数量 cnt：
- 若
cnt ≤ M，说明可以达到间距 ≥x； - 否则不可行。
3️⃣ 二分搜索范围
- 左边界：
0 - 右边界：
L（最大可能距离）
⏱️ 时间复杂度
- 检查函数
O(N) - 二分次数
O(log L) - 总复杂度：
O(N log L)，足够高效。
💻 C++ 参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long long L;
int N, M;
cin >> L >> N >> M;
vector<long long> d(N + 2);
d[0] = 0;
for (int i = 1; i <= N; i++) cin >> d[i];
d[N + 1] = L;
// 二分答案
long long l = 1, r = L, ans = 0;
while (l <= r) {
long long mid = (l + r) / 2;
int removed = 0;
long long last = 0;
for (int i = 1; i <= N + 1; i++) {
if (d[i] - last < mid) {
removed++; // 这块残骸太近，必须清理
} else {
last = d[i]; // 保留
}
}
if (removed <= M) {
ans = mid; // 可行，尝试更大距离
l = mid + 1;
} else {
r = mid - 1; // 不可行，缩小距离
}
}
cout << ans << "\n";
return 0;
}