解題說明
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）嚴格證明？
- 如果題目改為最大化每艘船的載重利用率，問題的性質會如何變化？