1. 题目描述
2. 思路分析
整体思路:二分答案
由题意知,公路上相邻路标的最大距离定义为该公路的“空旷指数”。在公路上增设一些路标,使得公路的“空旷指数”最小。也就是满足最大值最小。我们就自然想到可以二分答案。
定义三个变量L,n,k分别表示公路的长度,原有路标的数量,以及最多可增设的路标数量。开一个数组a,数组的第i个元素a[i]表示原有路标与起点的距离。
我们这里又开了一个差值数组s,令s[i]=a[i]-a[i-1],这样就可以用数组s表示原有的两个相邻路标的距离。
令左边界l=0,右边界r=L。
套用二分模板,mid=(l+r)>>1。主要就是要写一个check()函数,设check()函数的形参为x,将mid传入x。我们定义一个cnt变量用于记录新增的路标数量,遍历s[i]数组,如果s[i]>x,我们就要新增一个路标(cnt++),同时我们判断剩余部分(s[i]-x)的长度和x的关系,如果剩余部分的长度比x大,我们就继续插路标(cnt++),直到num<=x。
for循环结束后,我们判断一下cnt(新增路标数量)和k(最多可增设的路标数量),如果cnt<=k,return true。否则return false。
3. 代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
ll a[N], s[N], L, n, k, maxx;
bool check(int x) {
ll cnt = 0;
for (int i = 1; i <= n; i++) {
if (s[i] > x) {
cnt++;
int num = s[i] - x;
while (num > x) {
cnt++;
num -= x;
}
}
}
if (cnt <= k) return true;
else return false;
}
int main() {
cin >> L >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = a[i] - a[i - 1];
}
int l = 0, r = L;
while (l + 1 < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << endl;
return 0;
}