【题目来源】
洛谷：[P3853 TJOI2007] 路标设置 - 洛谷
【题目描述】
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
【输入】
第 \(1\) 行包括三个数 \(L,N,K\)，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 \(2\) 行包括递增排列的 \(N\) 个整数，分别表示原有的 \(N\) 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 \([0,L]\) 内。
【输出】
输出 \(1\) 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
【输入样例】
101 2 1
0 101
【输出样例】
51
【解题思路】
【算法标签】
《洛谷 P3853 路标设置》 #模拟# #搜索# #二分# #各省省选# #天津# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// length: 道路总长度
// n: 已有石头数量
// k: 可以移除的石头数量
// a[100005]: 存储相邻石头间的距离
// last: 记录前一个石头位置
// now: 当前石头位置
// l, r: 二分查找的左右边界
int length, n, k, a[100005], last, now, l, r;int main()
{// 输入道路总长度、已有石头数量和可移除石头数量cin >> length >> n >> k;last = 0; // 初始化前一个石头位置为起点0// 计算相邻石头间的距离for (int i = 0; i < n; i++){cin >> now;a[i] = now - last; // 计算当前石头与前一个石头的距离last = now; // 更新前一个石头位置}// 添加终点到最后一个石头的距离a[n] = length - last;// 特殊情况处理：不能移除任何石头时，直接返回道路总长度if (k == 0){cout << length;return 0;}// 初始化二分查找边界l = 1; // 最小跳跃距离至少为1r = 1e7; // 设置一个足够大的上界// 二分查找最小化最大跳跃距离while (l <= r){int mid = l + (r - l) / 2; // 计算中间值，防止溢出int count = 0; // 记录需要移除的石头数量// 计算在当前mid值下需要移除多少石头for (int i = 0; i <= n; i++){int tmp = a[i]; // 当前石头间距while (tmp > mid) // 如果间距大于mid，需要分割{count++; // 增加移除石头计数tmp -= mid; // 模拟移除石头后的剩余距离}}// 根据计算结果调整搜索范围if (count <= k){r = mid - 1; // 可以尝试更小的最大跳跃距离}else{l = mid + 1; // 需要更大的最大跳跃距离}}// 输出最终确定的最小化最大跳跃距离cout << l << endl;return 0;
}
【运行结果】
101 2 1
0 101
51