AcWing 519. 跳石头
原题链接
中等
作者:
刘帅哥
,
2023-08-08 19:28:24
,
所有人可见
,
阅读 76
//519
//运用二分就可以求出来
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int l, n, m;
int su[N];
bool check(int mid){
int last = 0, cnt = 0;
for (int i = 1; i <= n; i ++ )
if (su[i] - last < mid) cnt ++ ;
else last = su[i];
return cnt <= m;
}
int main(){
cin >> l >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> su[i];
su[++ n] = l;
int l = 1, r = 1e9;
while (l < r){
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r;
return 0;
}