最大化最小距離（牛棚放牛問題）

# 例題 ： # 題目： # 有 N 個牛棚位置（已排序），要放 K 頭牛， # 希望「任意兩頭牛之間的最小距離」最大化。 # 輸入： # ``` # 位置 = [1, 2, 8, 12, 17] # K = 3 # ``` # 期望輸出： # ``` # 最大化後的最小距離 = 7 # # 放在位置 1, 8, 17 # ``` # 思路： # 設最小距離為 d， # 若能成功放完 K 頭牛，代表 d 可行； # 否則 d 太大，需縮小。 # 用二分搜尋尋找最大的可行距離。 def can_place(a, k, d): count = 1 last = a[0] for x in a[1:]: if x-last >=d: count+=1 last=x if count==k: return True return False def max_min_d(a, k): a.sort() lo,hi = 0,a[-1]-a[0] while lo<=hi: m = (lo+hi)//2 if can_place(a,k,m): ans = m lo = m+1 else: hi = m-1 return ans print(max_min_d([1, 2, 8, 12, 17], 3)) # 7 # 重點概念： # 「距離越大越難放下」具有單調性 → 二分搜尋最大可行距離。