EasyRating 1296
3477. Fruits Into Baskets II
arraybinary-searchsegment-treesimulationordered-set
解題說明
Fruits Into Baskets II
題目描述：給定一個整數陣列 fruits（代表每棵果樹的水果數量）和一個整數陣列 baskets（代表每個籃子的容量）。對每個水果 fruits[i]，從左到右找到第一個容量 >= fruits[i] 且尚未使用的籃子放入。若找不到合適的籃子則跳過。回傳最終被放入籃子的水果數量。
解題思路：由於 Easy 版本的陣列長度較小，可以直接模擬。對每個水果，遍歷所有籃子找到第一個未使用且容量足夠的籃子。使用一個布林陣列標記已使用的籃子。
C++ 解法
複雜度分析
時間複雜度：O(n × m) — 每個水果最多遍歷所有籃子一次。
空間複雜度：O(m) — 布林陣列標記已使用的籃子。
虛擬碼
1. Initialize used[] = all false, placed = 0
2. For each fruit fruits[i]:
a. For each basket j from left to right:
If not used[j] and baskets[j] >= fruits[i]:
Mark used[j] = true, placed++, break
3. Return n - placed (unplaced count)其他解法
線段樹 O(n log m)：用線段樹維護可用籃子的容量，支援「查詢第一個 >= x 的位置」操作。每次查詢和更新為 O(log m)，總時間 O(n log m)。適用於大規模輸入。
有序集合（Ordered Set）O(n log m)：用 std::set 或 std::multiset 維護可用籃子的 (容量, 索引) 對。對每個水果用 lower_bound 找最小可用容量。但需要找「第一個位置」而非「最小容量」，較難直接用 multiset。
延伸思考
- 如果要找的不是「第一個足夠大的籃子」而是「容量最接近的籃子」（Best Fit），如何修改？
- 如果籃子可以重複使用（但每次使用後容量減少），問題如何變化？
- 如何用線段樹將暴力 O(n × m) 優化到 O(n log m)？