(二分查找)农夫和奶牛

一座很长的畜栏,包括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

上一篇:QStyle Tree Branch 样式设计 (二十五)


下一篇:C++:制作火把