Angry Cows(Silver)（二分）

题目：

数轴上n个点。k个炸弹，每个炸弹可以将一个长2R+1的区间覆盖。问覆盖n个点的，R的最小值。
n≤50000，k≤10

做法：

很明显可以二分R的值。然后O(n)check。具体就是贪心地用区间的左端点覆盖当前最左边的点，这样每个区间都发挥最大的作用。然后看覆盖n个点需要用几个区间，设为cnt，若cnt>k，说明R小了，l = mid+1，否则r = mid-1。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 5e4 + 7;
int n, k, a[N];
bool judge(int R){
    R <<= 1;
    int cnt = 0;
    for (int i = 1, j; i <= n; i = j){
        for (j = i; j <= n && a[j]-a[i] <= R; ++j);
        cnt++; if (cnt > k) return false;
    }
    return true;
}
int main(void){
    IOS;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a+1, a+n+1);
    int l = 0, r = 1e9, ans;
    while (l <= r){
        int mid = (l+r) >> 1;
        if (judge(mid)){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << ans << endl;
    return 0;
}