Aggressive Cows

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
3
Indexable
Never
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int    long long
#define endl '\n' 
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
typedef tree<int, null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> pbds;//A.find_by_order(x), A.order_of_key(x)
const long long INF=1e18;
const int mod=1e9+7;  // 998244353;

void dgb_out () { cerr << endl; }
template < typename Head, typename... Tail >
void dgb_out ( Head H, Tail... T) { cerr <<' ' << H; dgb_out (T...); }
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dgb_out(__VA_ARGS__) 
#else
#define dbg(...)
#endif
const int N = 1e5 + 5;
int n, c, x[N];
bool predicate(int num){
    int prev = x[0], cnt=1;
    for(int i=1;i<n;i++){
        if(x[i]-prev>=num){
            prev = x[i];
            cnt++;
        }
    }
    return cnt>=c;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.in","r", stdin);
//freopen("output.out","w", stdout);
//pbds A;
int tc=1;
cin>>tc;
while(tc--)
{
cin>>n>>c;
for(int i=0;i<n;i++)cin>>x[i];
sort(x, x+n);
int l=0, r = x[n-1] - x[0];
while(r-l>1){
    int mid = (l+r)/2;
    if(predicate(mid)){
        l = mid;
    }
    else{
        r = mid;
    }
} 
if(predicate(r)){
    cout<<r<<endl;
}
else{
    cout<<l<<endl;
}
}
    return 0;
}