Angry Cows(Silver)

答案是求最小,所以我们可以二分

如何

容易想到,最左边的那个牛肯定要被覆盖,假设他的位置是

那第一个爆炸点选在位置肯定是最优的

所以可以再次进行二分,双二分,没什么好说的

#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;
}