一组数据 11 3 0 4 8 10 不能移走石头,最小应该是1吧,但我自己的ac代码输出是2
#include<iostream>
#include<cstring>
#include<cstdlib>
#include <map>
#include <climits>
#include<algorithm>
#include <stack>
#include <deque>
#define ll long long
using namespace std;
#define MAX_N 1000005
int dis[MAX_N];
int l, m, n;
bool check(int len) {
int cnt = 0;
int pre = 0;
for (int i = 1; i <= n; i++) {
if ((dis[i] - dis[pre]) >= len) {
pre = i;
cnt++;
}
}
return cnt >= n - m;
}
int main(){
cin >> l >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> dis[i];
}
dis[0] = 0;
dis[n + 1] = l;
int left = 0;
int right = l;
int ans = l;
while (left <= right) {
int mid = (left + right) >> 1;
if (check(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << ans << endl;
return 0;
}
因为没有在check()的时候检查最后跳到n+1的那次长度