解題說明
Boats to Save People
題目描述:
給定一個整數陣列 people,其中 people[i] 是第 i 個人的體重,以及一個整數 limit 表示每艘船的載重上限。每艘船最多載兩人,且總重量不超過 limit。求最少需要幾艘船才能載完所有人。
解題思路: 排序 + 雙指標(貪心):
- 將
people排序。 - 使用左指標
lo(最輕的人)和右指標hi(最重的人)。 - 每次嘗試讓最重和最輕的人同船:
- 若
people[lo] + people[hi] <= limit,兩人共乘一船,lo++、hi--。 - 否則最重的人獨自一船,
hi--。
- 若
- 每輪消耗一艘船。
貪心正確性:最重的人若無法與最輕的人同船,則他無法與任何人同船,必須獨佔一艘。若能同船,讓最輕的人搭配是最優的(為其他人保留更大的配對空間)。
C++ 解法
複雜度分析
時間複雜度:O(n log n) — 排序為主要開銷,雙指標掃描為 O(n)。
空間複雜度:O(log n) — 排序所需的棧空間(原地排序)。
虛擬碼
1. Sort people array in ascending order. 2. Initialize lo = 0, hi = n - 1, boats = 0. 3. While lo <= hi: a. If people[lo] + people[hi] <= limit: increment lo (pair them). b. Decrement hi (heaviest person boards). c. Increment boats. 4. Return boats.
其他解法
計數排序 + 雙指標:若體重範圍有限(如 1 到 limit),可用計數排序將時間降至 O(n + limit)。適用於體重值域小的情況,但一般排序已足夠。
暴力枚舉配對:O(n^2) 嘗試所有配對。效率太低,不適用於大規模輸入。
延伸思考
- 如果每艘船最多可載三人,貪心策略該如何調整?雙指標是否仍然適用?
- 為什麼「最重配最輕」的貪心策略是最優的?能否用交換論證(exchange argument)嚴格證明?
- 如果題目改為最大化每艘船的載重利用率,問題的性質會如何變化?