My solution to http://www.spoj.com/problems/AGGRCOW

aggrcow.cpp

// AGGRCOW
// Aggressive cows

#include <bits/stdc++.h>
using namespace std;

#define ll int64_t
#define MAX 1e5

void aggrcow() {
	ll N, C;
	cin >> N >> C;

	ll x[N];
	for(ll i = 0; i < N; i += 1) {
		cin >> x[i];
	}
	
	std::sort(x, x+N); // O(n lg n)

	ll maxDistance = x[N-1] - x[0]; 
	ll minDistance = maxDistance; 
	for(ll i = 0; i < N - 1; i += 1) {
		minDistance = std::min(minDistance, x[i+1] - x[i]);
	}

	ll maxCows = 1, midDistance;

	while(minDistance <= maxDistance) {
		maxCows = 1; // max # of cows that can be separated using a distance equal to midDistance
		midDistance = minDistance + (maxDistance - minDistance + 1)/2;

		ll lastStallIndex = 0;
		for(ll i = 1; i < N; i += 1) {
			if(x[i] >= x[lastStallIndex] + midDistance) {
				maxCows += 1;
				lastStallIndex = i;
			}
		}

		if(maxCows < C) {
			maxDistance = midDistance - 1;
		}
		else if(maxCows >= C) {		
			if(minDistance == maxDistance) {
				break;
			}
			else {
				minDistance = midDistance;
			}
		}
	}
	cout << midDistance << endl;
}

int main() {
	ll t;
	cin >> t;
	while(t-- > 0) {
		aggrcow();
	}
	return 0;
}