题目描述
Farmer John 建造了一个有 $N$($2$ $\le$ $N$ $\le$ $100000$) 个隔间的牛棚,这些隔间分布在一条直线上,坐标是 $x_1$ ,…,$x_N$
(0 $\le$ $x_i$ $\le$ $1000000000$)。
他的 $C$($2$ $\le$ $C$ $\le$ $N$) 头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John 想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?
输入格式
第 $1$ 行:两个用空格隔开的数字 $N$ 和 $C$。
第 $2$ ~ $N+1$ 行:每行一个整数,表示每个隔间的坐标。
输出格式
输出只有一行,即相邻两头牛最大的最近距离。
样例 #1
样例输入 #1
5 3
1
2
8
4
9
样例输出 #1
3
算法1
(二分) $O(nlog_2n)$
先思考暴力做法:从小到大枚举两头牛之间的最短距离$dis$,若能满足条件:每头牛之间的距离都为$dis$时能放下$c$头牛,$dis++$,否则上一个$dis$就是最短距离的最大值。
优化:对于距离$dis$可以二分答案。
当长度为$dis$时能放置所有牛的概率$P\gt0$时,$ans$在$dis$右边,使$l=mid$,否则$r=mid-1$
时间复杂度
坐标排序$O(nlog_2n)$,二分距离$O(log_2n)$。
参考文献
《算竞》
Python 代码
n,m=map(int,input().split())
def check(x):
plc=0 #当前最后一头奶牛放的位置
cnt=1 #当前放置的奶牛数量
for i in range(1,n):
if a[i]-a[plc]>=x:
cnt+=1
plc=i
return cnt>=m
def bisearch():
l=0
r=a[n-1]-a[0]
while l<r:
mid=l+r+1>>1 #mid为最短距离
if check(mid):
ans=mid
l=mid
else:
r=mid-1
return l
a=[0]*n
for i in range(n):
a[i]=int(input())
ans=0
a.sort()
print(bisearch())