SPOJ - Aggressive Cows (AGGRCOW) Problems Solution

SPOJ -  Aggressive Cows (AGGRCOW) Problems Solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 100010
#define ll long long

ll arr[MAX];
int tc,N,C;

bool func(int mid)
{
    int cows=1,pos=arr[0];

    for(int i=1;i<N;i++)
    {
        if(arr[i]-pos>=mid)
        {
            pos=arr[i];
            cows++;
            if(cows==C)
                return 1;
        }
    }
    return 0;
}

int cal_dist()
{
    int lo,hi,mid,max_dist=-1;
    lo=0;
    hi=arr[N-1];

    while(lo<hi)
    {
        mid=lo+(hi-lo)/2;

        if(func(mid)==1)
        {
            if(mid>max_dist)
                max_dist=mid;
            lo=mid+1;
        }
        else
            hi=mid;
    }
    return max_dist;
}

int main()
{
    cin>>tc;
    while(tc--)
    {
        cin>>N>>C;
        for(int i=0;i<N;i++)
            cin>>arr[i];

        sort(arr,arr+N);

        cout<<cal_dist()<<endl;
    }
    return 0;

}