NC24017（Angry Cows(Silver) ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<ll> pos;
int n, num;
ll v;
bool check(ll R){
    if(R < 0) return false;
    ll c = pos[0]; int res = num - 1;
    while(true){
        auto it = upper_bound(pos.begin(), pos.end(), c + 2 * R);
        if(it == pos.end()) return true;
        if(!res) break;
        c = *it; res--;
    }
    return false;;
}
int main(){
    scanf("%d%d", &n, &num);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &v);
        pos.push_back(v);
    }
    sort(pos.begin(), pos.end());
    ll l, r, mid;
    l = -1; r = 1e9;
    while(r - l > 1){
        mid = (l + r) / 2;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid;
        }
    }
    printf("%lld\n", r);
    return 0;
}