题解 | #[USACO 2016 Jan S]Angry Cows#

//寻找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;
}