解题思路
弱弱的写一个二分答案
可以通过二分的思想,判断该 mid 是否可以作为最小距离的最大值,如果可以便更新左边界(最小值最大化)。
那么如何判断是否可以作为最小距离的最大值呢?
这里有一点贪心的思想,可以判断当前点距离上一个点的距离是否大于等于 mid,如果不满足便拿掉该块石头,如果拿掉的石头数量超过 m 个,也说明该 mid 不满足。
code
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 50005
int arr[MAXN];
int e, n, m;
int check(int x) {
int last = 0, now, cnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] - last < x) {
if (i == n - 1 || cnt == m) return 0;
cnt += 1;
} else {
last = arr[i];
}
}
return 1;
}
int solve() {
int l = 0, r = e, mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> e >> n >> m;
for (int i = 0; i < n; i++) cin >> arr[i];
arr[n++] = e;
cout << solve() << endl;
return 0;
}
文章评论