Angry Cows(Silver)
Angry Cows(Silver)
https://ac.nowcoder.com/acm/problem/24017
答案是求最小,所以我们可以二分
如何
容易想到,最左边的那个牛肯定要被覆盖,假设他的位置是
那第一个爆炸点选在位置肯定是最优的
所以可以再次进行二分,双二分,没什么好说的
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int a[maxn],k,n;
bool isok(int mid)
{
int now=1,s=k;
while( now<=n )
{
int nxt = upper_bound(a+now,a+1+n,a[now]+mid*2)-a;
now = nxt;
s--;
}
return s>=0;
}
int main()
{
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+1+n);
int l=0,r=1000000000,mid,ans=0;
while( r>=l )
{
mid = l+r>>1;
if( isok(mid) ) r=mid-1,ans=mid;
else l=mid+1;
}
cout << ans;
}