題目描述:給定一個整數陣列 weights 代表每個包裹的重量,以及一個整數 days,代表必須在 days 天內將所有包裹依序運送完畢。船每天按照 weights 陣列的順序裝載包裹,不能超過船的最大承載量。求能在 days 天內運完所有包裹的船的最小承載量。
解題思路:本題的關鍵在於觀察到答案具有「單調性」:若某個承載量 cap 能在 days 天內運完,則任何大於 cap 的承載量也能做到。因此可以對答案進行二分搜尋。
搜尋範圍:
max(weights),因為至少要能裝下最重的單個包裹sum(weights),即一天全部運完對於每個候選承載量 mid,使用貪心模擬:從左到右依序將包裹加入當天的行程;若加入下一個包裹會超重,則換新的一天。最後統計需要幾天,若 ≤ days 則 mid 是可行的,嘗試更小的值;否則需要增大承載量。
貪心正確性:每天盡量多裝包裹(但不超重)是最優策略,因為這樣能最小化天數。
時間複雜度:O(n log(sum)) — 二分搜尋的範圍是 [max(weights), sum(weights)],共 O(log(sum)) 次迭代;每次迭代呼叫 canShip 需 O(n) 時間掃描所有包裹。
空間複雜度:O(1) — 只使用了常數個額外變數,不計輸入陣列本身。
1. Set lo = max element in weights (minimum possible capacity)
2. Set hi = sum of all weights (maximum possible capacity)
3. While lo < hi:
a. mid = lo + (hi - lo) / 2
b. Simulate shipping with capacity = mid:
- Initialize daysNeeded = 1, currentLoad = 0
- For each weight w in weights:
- If currentLoad + w > mid: increment daysNeeded, reset currentLoad = 0
- Add w to currentLoad
c. If daysNeeded <= days: hi = mid (mid is feasible, try smaller)
d. Else: lo = mid + 1 (mid is too small, need more capacity)
4. Return lo線性掃描 O(n · sum):直接從 max(weights) 開始逐一嘗試每個承載量,對每個值模擬計算天數。時間複雜度過高,對大輸入不可行,僅作為概念驗證。
前綴和 + 二分 O(n log n):預先計算前綴和陣列,在 canShip 中用二分搜尋找每天能裝多少包裹,避免線性掃描。雖然每次 canShip 降至 O(log n),但整體仍是 O(n log n)(n 次二分),與標準解法接近;實作更複雜,優化幅度有限,通常不值得。