297 Aggressive cows

cowsgrrrrrr.cpp

//http://www.spoj.com/problems/AGGRCOW/
#include <cstdio>
#include <algorithm>

using namespace std;

bool feasible(int *a, int n, int c, int dist) {
    int last = 0; int cows = 1;
    for(int i = 1; i < n; i++) {
        if(a[i]-a[last] >= dist) {
            cows+=1;
            last = i;
            if(cows >= c) return true;
        }
    }
    return false;
}

int main() {
    int t, n, c;
    int stalls[100005];
    int left, right, mid, ans;
    scanf("%d", &t);
while(t--) {
    scanf("%d %d", &n, &c);
    for(int i = 0; i < n; i++) scanf("%d", &stalls[i]);
    sort(stalls,stalls+n);
    left = 1; right = stalls[n-1]-stalls[0];
    ans = 0;
    while(left <= right) {
        mid = (left+right)/2;
        //printf("left: %d right: %d mid: %d\n", left, right, mid);
        if(feasible(stalls,n,c,mid)) {
            if(mid > ans) ans = mid;
            left = mid+1;
            //printf("%d es viable, cambiando left\n", mid);
        }
        else {
            right = mid-1;
            //printf("%d no es viable, cambiando right\n", mid);
        }
    }
    //printf("ultimo left: %d, ultimo right: %d, ultimo mid: %d\n", left, right, mid);
    printf("%d\n",ans);
}
    return 0;
}