34 lines
1011 B
C++
34 lines
1011 B
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 100010;
|
||
int a[N];
|
||
int L;//表示公路的长度
|
||
int n;//原有路标的数量
|
||
int K;//最多可增设的路标数量
|
||
|
||
bool check(int mid) {
|
||
//如果按空旷指数 mid进行安排，那么需要安排几个路标
|
||
int t = 0; //需要增加的路标个数
|
||
for (int i = 1; i < n; i++)
|
||
if (a[i + 1] - a[i] > mid) {
|
||
t += (a[i + 1] - a[i]) / mid;
|
||
//如果余数为零，还是要减去一个滴~
|
||
if ((a[i + 1] - a[i]) % mid == 0) t--;
|
||
}
|
||
return t <= k;//如果现在的路标数量小于k,也还行？~
|
||
}
|
||
|
||
int main() {
|
||
cin >> L >> n >> k;
|
||
for (int i = 1; i <= n; i++) cin >> a[i];
|
||
|
||
int l = 0, r = L;
|
||
while (l < r) {
|
||
int mid = l + r >> 1;
|
||
if (check(mid)) r = mid; // 使得公路的“空旷指数”最小,向小了逼近，r=mid
|
||
else l = mid + 1;
|
||
}
|
||
cout << l << endl;
|
||
return 0;
|
||
} |