Angry Cows(Silver)(二分)

Angry Cows(Silver)

思路

套路二分，我们枚举左端点，把炸弹放到中间，然后check右端点是否在区间，

如果不在区间就重新确定一个爆炸区间范围，投放次数加一，

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;

int a[N], k, n;

bool judge(int x) {
    int sum = 0, last = -2 * x;
    for(int i = 1; i <= n; i++) {
        if(last < a[i] - x) {
            sum++;
            last = a[i] + x;
        }
    }
    return sum <= k;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int l = 0, r = 1e9 + 10;
    while(l < r) {
        int mid = l + r >> 1;
        if(judge(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
    return 0;
}