P1824 进击的奶牛

对于一个值x，如果能够满足牛之间的最短距离>= x，则所有小于等于x的值t均能够满足存在一种安排方法能够使奶牛之间的最短距离大于等于t。所以可以二分找最短距离的最大值。
复杂度：(O(nlog(1e9)))

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int a[N];
int n, c;

int check(int x){
    int last = 0, cnt = 1;
    for(int i = 1; i < n; i ++){
        if(a[i] - a[last] < x) continue;
        last = i, cnt ++;
    }
    
    return cnt >= c;
}

int main(){
    cin >> n >> c;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    sort(a, a + n);
    
    int l = 1, r = 1e9;
    
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    
    cout << l << endl;
    
    return 0;
}