#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int inf=0x7fffffff;
const int ms=100004;
int d[ms];
int N,C;
bool judge(int dis)
{
	int last=0;
	for(int i=1;i<C;i++)
	{
		int tmp=last+1;
		while(tmp<N&&d[tmp]<(d[last]+dis))
			tmp++;
		if(tmp==N)
			return false;
		last=tmp;
	}
	return true;
}
void solve()
{
	sort(d,d+N);
	int begin=0,end=inf;
	while(end-begin>1)
	{
		int mid=(begin+end)/2;
		if(judge(mid))
			begin=mid;
		else
			end=mid;
	}
	printf("%d\n",begin);
	return ;
}
int main()
{
	scanf("%d%d",&N,&C);
	for(int i=0;i<N;i++)
		scanf("%d",&d[i]);
	solve();
	return 0;
}

• Re:二分 (61) Alanqky 2014-11-29 15:09:16