题解 | #[USACO 2016 Jan S]Angry Cows#
[USACO 2016 Jan S]Angry Cows
https://ac.nowcoder.com/acm/problem/24017
寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了如果验证当前的R可以将草堆全部引爆。
如何验证：从左向右去炸第一问即可，在其中维护一个当前爆炸的最大坐标从而来判断当前这个草堆是不是需要去炸的第一个就可以了。
//寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了如果验证当前的R可以将草堆全部引爆。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50000+10;
int N, K;//N干草的数量，K奶牛的数量
int hay[maxn];
bool yanz(int k)
{
int cao = K;
int j = 0;
int total = k*2;
for (int i=0;i<N;i++) {
if (hay[i]>j) {
cao--;
j = total+hay[i];
};
}
if (cao>=0) return true;
else return false;
}
int main() {
int k;
cin>>N>>K;
for (int i=0;i<N;i++) {
scanf("%d", &hay[i]);
}
sort(hay, hay+N);
int l = 1, r = hay[N-1];
//二分答案
while (l<r) {
int mid = (l+r)/2;
if (yanz(mid)) r = mid;
else l = mid+1;
}
// cout<<yanz(5)<<endl;
cout<<l<<endl;
return 0;
}
