首页 > 其他 > 详细

(二分查找)农夫和奶牛

时间:2020-02-25 15:11:26      阅读:108      评论:0      收藏:0      [点我收藏+]

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

(二分查找)农夫和奶牛

原文:https://www.cnblogs.com/lijiahui-123/p/12361770.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!