题目描述
Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots cows with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. Each cow lands with sufficient force to detonate the hay bales in close proximity to her landing site. The goal is to use a set of cows to detonate all the hay bales.
There are N hay bales located at distinct integer positions x1,x2,…,xN on the number line. If a cow is launched with power R landing at position x, this will causes a blast of "radius R", destroying all hay bales within the range x−R…x+R.
A total of K cows are available to shoot, each with the same power R. Please determine the minimum integer value of R such that it is possible to use the K cows to detonate every single hay bale in the scene.
输入描述
The first line of input contains N (1≤N≤50,000) and K (1≤K≤10). The remaining N lines all contain integers x1…xN (each in the range 0…1,000,000,000).
输出描述
Please output the minimum power R with which each cow must be launched in order to detonate all the hay bales.
示例1
输入
7 2
20
25
18
8
10
3
1
输出
5
知识点:二分。
显然二分半径,由于覆盖范围是 \([x-R,x+R]\) 从 \(x-R\) 开始到另一点 \(x+R\) 一共距离 \(2R\) ,所以从之前一个点 \(a_{pre}\) 开始,到某个点 \(a_{pos}\) 的距离满足 \(a_{pos} - a_{pre}>2R\) 时,则让 \(a_{pos}\) 成为下一个 \(a_{pre}\) ,然后区域数 \(cnt\) 加一。如果最后 \(cnt \leq k\) ,则说明可行;\(cnt>k\),则说明不可行。
时间复杂度 \(O(n \log \lceil \frac{a[n-1]-a[0]}{2} \rceil)\)
空间复杂度 \(O(n)\)
#include <bits/stdc++.h>
using namespace std;
int a[50007];
int n, k;
bool check(int mid) {
int pre = a[0], cnt = 0;
for (int i = 1;i < n;i++) {
if (a[i] - pre > 2 * mid) {
cnt++;
pre = a[i];
}
}
cnt++;
return cnt <= k;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 0;i < n;i++) cin >> a[i];
sort(a, a + n);
int l = 1, r = (a[n - 1] - a[0] + 1) / 2;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l << '\n';
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章