MediumRating 2178
3479. Fruits Into Baskets III
arraybinary-searchsegment-treeordered-set
解題說明
Fruits Into Baskets III
題目描述：給定一個整數陣列 fruits，其中 fruits[i] 代表第 i 棵果樹的水果種類，以及一個整數陣列 baskets，其中 baskets[j] 代表第 j 個籃子的容量上限。對於每棵果樹（按順序），需要找到編號最小的籃子，使得該籃子的容量大於等於水果種類編號，並且該籃子尚未被使用。若找到則放入該籃子（籃子標記為已使用），否則該水果被丟棄。回傳一個陣列，表示每棵果樹的水果最終放入哪個籃子（若被丟棄則為 -1）。
解題思路：核心挑戰在於對每個水果快速找到「容量 >= fruits[i] 且編號最小的未使用籃子」。可以用線段樹維護籃子的最大容量：建立一棵線段樹，每個節點儲存其區間內所有未使用籃子的最大容量。查詢時，優先走左子樹，若左子樹的最大值 >= fruits[i]，就往左子樹找；否則往右子樹找。找到後，將該籃子的容量設為 0（標記為已使用），並向上更新最大值。這樣每次查詢和更新都是 O(log n)。
C++ 解法
複雜度分析
時間複雜度：O((n + m) log n) — 建樹 O(n)，每個水果的查詢與更新各 O(log n)，共 m 個水果。
空間複雜度：O(n) — 線段樹所需的額外空間。
虛擬碼
1. Build a segment tree over baskets[], where each node stores the max value in its range
2. For each fruit i (0 to m-1):
a. Query the segment tree: find leftmost index where baskets[idx] >= fruits[i]
- At each node, if left child max >= fruits[i], recurse left; else recurse right
b. If found (idx != -1): set result[i] = idx, update tree to set baskets[idx] = 0
c. If not found: set result[i] = -1
3. Return result array其他解法
有序集合 (Ordered Set) O(m log n)：使用 std::set<pair<int,int>> 儲存 (容量, 索引)。對每個水果，用 lower_bound 找到容量 >= fruits[i] 的最小容量，再從中選最小索引。但需要處理同容量多籃子的情況，較難直接取最小索引。
暴力法 O(n * m)：對每個水果遍歷所有籃子找第一個可用的，超時但實作簡單，適合驗證正確性。
延伸思考
- 如果籃子可以被重複使用（放完後釋放），該如何修改演算法？
- 如果要最大化放入籃子的水果總數而非按順序處理，如何建模為匹配問題？
- 若水果和籃子的數量都非常大（10^6），有沒有離線做法可以進一步優化？