一座很长的畜栏,包括N(2<=N<=100000)个隔间,这些小隔间的位置为x0,....xN-1(0<=xi<=1000000000,均为整数,各不相同)
将C(2<=C<=N)头奶牛每头分到一个隔间。牛都希望相互离得远,怎样才能使任意两头牛之间的最小距离尽可能的大,这个最小距离是多少?
题解:
先将坐标排序
这个最大距离在(0,1000000000/C]区间中,在[L,R]内用二分法尝试最大距离D=(L+R)/2(L,R初值为1,1000000000)
若D可行,则记住D,然后在新[L,R]中继续尝试(L=D+1)
若D不可行,则在新[L,R]中继续尝试(R=D-1)
复杂度log(1000000000/C)*N