http://www.spoj.com/problems/AGGRCOW/

main.cc

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
inline bool can(vector<ll>& points, ll max_dist, int c) {
    ll curr_dist = 0;
    int cc = 1;
    for (int i = 1; i < points.size(); ++i) {
        curr_dist += points[i] - points[i - 1];
        if (curr_dist >= max_dist) {
            ++cc;
            curr_dist = 0;
        }
    }
    return cc >= c;
}
 
int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    srand(time(0));
 
    int t, n, c;
    cin >> t;
    while (t --> 0) {
        cin >> n >> c;
        vector<ll> points(n);
        for (int i = 0; i < n; ++i) cin >> points[i];
        sort(begin(points), end(points));
        ll l = 0, r = (ll) 1e10, mid, ans;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (can(points, mid, c)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}