蓝桥杯备考：二分答案之路标设置
最大距离，找最小空旷指数值，我们是很容易想到用二分的，我们再看看这个答案有没有二段性
是有这么个二段性的，我们只要二分就行了，但是二分的check函数是有点不好想的，我们枚举空旷值的时候，为了达成该空旷值，我们要在每两个路标之间插入路标，我们最好的插法就是平均插，因为靠右一点或者靠左一点都会导致极值偏大，只有最平均的情况才是去掉极值的好方法
当然如果是0~6有个路标，我们目标达成的最大空旷值是2，
我们是需要两块板子的，也就是6/2-1
当然，如果两个路标之间距离是奇数个距离的话
我们就要插三块板子也就是7/2个板子
好的，话不多说我们来实现一下我们的代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int len, n, k;
int a[N];
bool check(int x)
{
int cnt = 0;
for (int i = 1; i < n; i++)
{
int d = a[i + 1] - a[i];
cnt += d/x - 1;
if (d %x )
{
cnt++;
}
}
return k >= cnt;
}
int main()
{
cin >> len >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int l = 1, r = len;
while (l < r)
{
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}