AcWing 519. 跳石头
原题链接
中等
作者:
CqAq
,
2024-03-30 12:53:32
,
所有人可见
,
阅读 2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5E4 + 9;
ll L, n ,m, a[N];
//最短距离为mid的情况下,移动的石头数
int check(int mid){
ll res = 0, lst = 0;
for(int i = 1; i <= n; ++ i){
if(a[i] - a[lst] < mid) {
res ++;
continue;
}
lst = i;
}
if(L - a[lst] < mid) return m + 1;//此时的mid不合法,超过了两岸的距离
return res;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> L >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> a[i];
ll l = 0, r = 1e9 + 4;
while(l < r){
ll mid = l + r + 1 >> 1;
if(check(mid) <= m) l = mid;//mid小了,可以更大
else r = mid - 1;
}
if(n == m) cout << L;
else cout << l << '\n';
return 0;
}