很多人忘记处理边界条件,就是第一块石头和起点的距离、最后一块石头和终点的距离
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
int arr[N];
int len, n, m;
// 核心思想:跳跃距离越大,需要移走的石头越多
// 那么可以分成两个区间,不能移走m块及以上的石头和能移走m块以上的石头
// 很明显我们的答案在第一个区间的右界,即答案区间在[mid, r]
bool check(int x){
int cnt = 0, last = 0; // 初始是检查第一块石头和起点的距离
for(int i = 1; i <= n; ++ i){
if(arr[i] - arr[last] < x) cnt ++;
else last = i;
}
// 检查终点的石头
if(len - arr[last] < x) cnt ++;
return cnt <= m;
}
int main(){
cin >> len >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> arr[i];
int l = 1, r = len;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}