oavoservice 原創講解：典型「二分答案」題，關鍵是把可行性寫成單調函數。
題目（改寫版）
給你 orders[i] 表示第 i 家餐廳需要處理的訂單量。你有 d 個 dasher。
規則：
- 每個 dasher 的最大處理量是
k。 - 一個餐廳的訂單可以分配給多個 dasher。
- 但一個 dasher 只能服務一個餐廳（不能跨餐廳接單）。
問最小的 k 是多少，使得所有訂單都能被 d 個 dasher 覆蓋。
關鍵觀察：可行性檢查
如果某個餐廳訂單量為 x，每個 dasher 最多處理 k，那麼該餐廳需要的 dashers 數量：
need = ceil(x / k)
把所有餐廳的 need 相加，若 sum_need <= d，則 k 可行。
隨著 k 增大，sum_need 單調不增，所以可以二分。
複雜度
- 可行性檢查：
O(n) - 二分搜尋：
O(log max(orders)) - 總計：
O(n log max(orders))
Python 參考實作
from math import ceil
def min_capacity(orders, d):
if not orders:
return 0
# 下界：至少要能處理某個餐廳的 1 個訂單；更緊的下界是 max(ceil(x/d)) 但這裡用 1 或 max(orders)//d 也行
lo, hi = 1, max(orders)
def feasible(k):
total = 0
for x in orders:
total += (x + k - 1) // k # ceil
if total > d:
return False
return True
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
面試官常問
- 為什麼
feasible(k)單調？（k 越大，單餐廳需要 dashers 越少或不變） - 為什麼
hi = max(orders)足夠？（k 等於最大餐廳訂單量時，每家餐廳最多 1 個 dasher） - 你如何防止溢出/超時？（提前剪枝：
total > d立刻返回）
DoorDash 這類題非常喜歡用來考「二分答案」套路。oavoservice 的訓練重點是：把業務約束翻譯成 ceil 公式，然後秒寫 feasible。
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。
联系方式
Email: [email protected] Telegram: @OAVOProxy