X003 路标设置
大约 2 分钟
X003 路标设置
【算法】 二分答案、贪心
【C++】 二分、贪心验证、排序
【难度】 普及/提高−
一、题目简述
一条公路长 ,原有 个路标(位置不一定有序)。至多可以增设 个路标,使得相邻路标之间的最大距离(称为"空旷指数")尽可能小。求最小的空旷指数。
数据范围:,,。
二、解题思路
1. 问题类型
这是一个最小化最大值问题:在限制增设数量的前提下,让最长的间距尽可能小。
2. 为什么能用二分
单调性:设空旷指数为 。如果 能通过至多 个新增路标实现,那么任何大于 的值也能实现(间距要求更宽松)。如果 不行,更小的 更不行。
判定结果从"不可行"变为"可行",单调切换,符合二分条件。
3. check 函数设计
check(d):遍历每一对相邻路标,如果间距 ,需要在中间插入路标。
插入多少个?间距为 ,要求每段 ≤ ,至少需要分成 段。
一段路标本身已有 2 个端点(即 1 段),所以需要插入的路标数 = 。
用整数运算避免浮点:插入数 = (等价于 ,请自行验证)。
累加所有插入数,若 ≤ 则可行。
4. 注意排序
输入的路标位置不一定有序,需先 sort。
5. 手动模拟
,路标位置 (排序后),:
d = 30:
- 间距 50(=60-10):需插入 (50-1)/30 = 1 个
- 间距 30(=90-60):需插入 (30-1)/30 = 0 个
- 总插入 1 ≤ K=2 ✅
d = 20:
- 间距 50:需插入 (50-1)/20 = 2 个
- 间距 30:需插入 (30-1)/20 = 1 个
- 总插入 3 > K=2 ❌
答案 = 30。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int L, n, K;
bool check(int d) {
int cnt = 0;
for (int i = 1; i < n; i++) {
int gap = a[i+1] - a[i];
if (gap > d) cnt += (gap - 1) / d;
}
return cnt <= K;
}
int main() {
cin >> L >> n >> K;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = L, ans = L;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) { ans = mid; r = mid - 1; }
else l = mid + 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序 ,二分共 轮,每轮遍历 个间距。
- 空间复杂度:,存储路标位置数组。
