题意

求最小的最长路牌间距（“空旷指数”最小）

思路

这道题和跳石头的思路差不多，也是二分找答案，改改 check() 就行了

check()

我们统计一下当前答案需要新增几个路牌，和最大新增路牌比较。

注意，如果两个路牌间隔过大，可能要新增多个路牌

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int R,n,m;
bool check(int x){
	int cnt = 0;
	for (int i = 1;i < n;i++){
		// 间隔减 1 就是新增路牌数
		cnt += ceil((a[i] - a[i - 1]) * 1.0 / x) - 1;
	}
	return cnt <= m;
}
int main(int argc, char **argv){
	cin >> R >> n >> m;
	for (int i = 0;i < n;i++){
		cin >> a[i];
	}
	int l = 0,r = R;
	while (l < r){
		int mid = (l + r + 1) >> 1;
		if (check(mid))	r = mid - 1;
		else	l = mid;
	}
	cout << l + 1;
	return 0;
}