「最小值」最大化：牛棚問題

 # 牛棚問題

# 題目： 在長度為 d 的一條線上，有 n 個牛棚位置，要放 k 頭牛，使得任兩牛距離的「最小值」最大化。

def can_place(positions,k ,min_dist):

  count = 1

  last = positions[0]

  for pos in positions[1:]:

    if pos > last + min_dist:

      count+=1

      last = pos

  return count >=k

positions = [1,2,8,4,9]

positions.sort()

k = 3

lo,hi = 1,positions[-1]-positions[0]+1

ans = 0

while lo<=hi:

  mid = (lo+hi)//2

  if can_place(positions,k,mid):

    ans = mid

    lo = mid +1

  else:

    hi = mid-1

    

print('最大最小距離：',ans)

Output:

最大最小距離： 2