Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN (0<=xi<=1,000,000,000)。
他的C(2<=C<=N)头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？
题解：
快排，二分。
代码：
varn,c:longint;f:array[1..100000]of longint;
procedure qsort(i,j:longint);
varl,r,t,mid:longint;
beginl:=i;r:=j;mid:=f[(j+i)div 2];repeatwhile f[j]>mid do dec(j);while f[i]<mid do inc(i);if i<=j thenbegint:=f[j];f[j]:=f[i];f[i]:=t;inc(i);dec(j);end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);
end;
function find(c,mid:longint):boolean;
varl,i,j:longint;s:boolean;
begins:=true;l:=1;for j:=2 to n dobeginif s thenif f[j]-f[l]<mid thens:=falseelsebegin dec(c);l:=j;endelseif f[j]-f[l]>=mid thenbegindec(c);l:=j;s:=true;end;if c=0 then break;end;if c=0 then find:=trueelse find:=false;
end;
procedure init;
vari,l,r,mid:longint;
beginreadln(n,c);for i:=1 to n doreadln(f[i]);qsort(1,n);l:=1;r:=(f[n]-f[1])div (c-1);while l<r dobeginmid:=(r+l) div 2;if find(c-1,mid) then l:=midelse r:=mid;if r-l=1 then break;end;if find(c-1,r) then writeln(r)else writeln(l);
end;
beginassign(input,'aggr.in');reset(input);assign(output,'aggr.out');rewrite(output);init;close(input);close(output);
end.
