。。。传送门。。。
http://www.spoj.pl/problems/AGGRCOW/。。。
二分+贪心麻。。很明显如果知道答案越往钱放越好嘛。。。
代码太短了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;int N,C,X[maxn];
bool Can(int limit)
{
int old=0,now=1;
for(int i=1;i<C;i++)
{
while(X[now]-X[old]<limit&&now<N)
now++;
if(now>=N)
return false;
old=now;now++;
}
return true;
}
void solve();
int main()
{
int t;cin>>t;
while(t–)
{       
solve();
}
}
void solve()
{
cin>>N>>C;
for(int i=0;i<N;i++)
scanf("%d",X+i);
sort(X,X+N);
int l=1,r=X[N-1];
while(l+1<r)
{
int mid=(l+r)/2;
if(Can(mid))
l=mid;
else
r=mid;
}
cout<<l<<endl;
}