题目信息
题目来源：CCF 天津省选 2007；
在线评测地址：Luogu#3853；
运行限制：时间 (1.00 extrm{s})，空间 (128 extrm{MiB})。
题目背景
B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路「空旷指数」。
题目描述
现在政府决定在公路上增设一些路标，使得公路的「空旷指数」最小。他们请求你设计一个程序计算能达到的最小值是多少。
请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
输入格式
第一行包括三个数 (L)、(N)、(K)，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第二行包括递增排列的 (N) 个整数，分别表示原有的 (N) 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 ([0,L]) 内。
输出格式
输出一行，包含一个整数，表示增设路标后能达到的最小「空旷指数」值。
数据规模及约定
- 对于 (50\%) 的数据，(2le Nle 100)，(0le Kle 100)；
- 对于 (100\%) 的数据中，(2le Nle 10^5)，(0le Kle 10^5)，(0<Lle 10^7)。
分析
求相邻路标距离最大值的最小答案，可以尝试用二分答案解决。
显然，这样转化后问题就是「隔一定距离放路标最少放几个」，易证这隔问题的答案满足单调性。我们二分找到答案 (le K) 的最大值，也就是路标数量的最小值。
注意事项
路障数 (=) 分割后的最小段数 (-1=leftlceildfrac{N}{d} ight ceil-1)（(d) 为最大距离）。而不是 (leftlfloordfrac{N}{d} ight floor)。
Code
#include <cstdio>
using namespace std;
const int max_n = 100000;
int diff[max_n], n, k;
inline int ceiling_div(int a, int b) { return (a % b)? (a/b+1):(a/b); } // 计算 ceil(n/d)
bool judge(int dis) // 判断
{
int ans = 0; // 统计数量
for (int i = 1; i < n; i++)
ans += ceiling_div(diff[i-1], dis) - 1;
return ans <= k; // 判断
}
int main()
{
int l, ta, tb, lb, ub, mid, ans = -1;
scanf("%d%d%d%d", &l, &n, &k, &ta); // 输入
for (int i = 1; i < n; i++)
{
scanf("%d", &tb);
diff[i-1] = tb - ta; // 我的做法是直接转换成差分数组
ta = tb;
}
lb = 0, ub = l;
while (lb < ub) // 二分 [lb,ub)
{
mid = (lb + ub) >> 1; // 中间
if (judge(mid))
ub = mid, ans = mid; // 可以就继续找更优的答案
else
lb = mid + 1; // 否则说明不够多
}
printf("%d
", ans);
return 0; // 然后就 AC 了、
}