ADOMINO - Arranging Dominoes

ADOMINO - Arranging Dominoes

no tags 

Dominoes have long entertained both game enthusiasts and programmers for quite some time. Many games can be played with dominoes, including multiplayer and single player games. Hari Khan has come up with a single player game. He takes N boxes and arranges them in a row at positions N1, N2 ... NN. Now he has to place D dominoes (D <=N) in the boxes such that the minimum distance between any two filled boxes is maximized.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

The first line of each test case consists of two integers, N <= 100000 and D <= N, separated by a single space.

N lines follow, each containing a single integer Ni <= 1000000000, indicating the location of the ith box.

Output

For each test case, output a single line containing a single integer denoting the largest minimum distance achievable between any two boxes with dominoes.

Example

Input:
1
5 3
1
2
3
4
5

Output:
2

#include<iostream>
using namespace std;
#include<algorithm>
 int  main()
 {
  long long int  t;
   cin>>t;
   while(t--)
    {
    long long int  n,c;
     cin>>n>>c;
     long long int  arr[n+5];
     for(long long int  i=0;i<n;i++)
      {
      cin>>arr[i];
      }
      sort(arr,arr+n);
    long long int  hi=arr[n-1]-arr[0];
    long long int  lo=0;
    /*for(long long int  i=0;i<n-1;i++)
     {
      if(arr[i+1]-arr[i]<lo) lo=arr[i+1]-arr[i];
     }
     */
     long long int  mid;
   //  cout<<"ini lo "<<lo<<" hi "<<hi<<endl;
     int ans=-1;
     while(lo<hi)
      {
      long long int  taken=1;
      long long int  last_pos=0;
          mid=(lo+hi)/2;
             //cout<<"mid "<<mid<<endl;
         for(long long int  i=1;i<n;i++)//  n-1
          {
          // cout<<"arr[last] "<<arr[last_pos]<<" arr[i ] "<<arr[i]<<endl;
          if(arr[i]-arr[last_pos]>=mid)
          {
          taken++;
          last_pos=i;
          }
          }
        //  cout<<"taken "<<taken<<endl;
         
          if(taken<c)
           {
            hi=mid;
           }
           else
           {
            if(ans<mid)
            ans=mid;
            lo=mid+1;
           }
      }
      cout<<ans<<endl;
     
    }
    return 0;
 }