指尖劃過的軌跡，藏着最細膩的答案~

題目：

給你兩個長度為 n 的整數數組，fruits 和 baskets，其中 fruits[i] 表示第 i 種水果的 數量，baskets[j] 表示第 j 個籃子的 容量。

你需要對 fruits 數組從左到右按照以下規則放置水果：

• 每種水果必須放入第一個 容量大於等於 該水果數量的 最左側可用籃子 中。
• 每個籃子只能裝 一種 水果。
• 如果一種水果 無法放入 任何籃子，它將保持 未放置。 返回所有可能分配完成後，剩餘未放置的水果種類的數量。

示例 1

輸入： fruits = [4,2,5], baskets = [3,5,4]
輸出： 1
解釋：

• fruits[0] = 4 放入 baskets[1] = 5。
• fruits[1] = 2 放入 baskets[0] = 3。
• fruits[2] = 5 無法放入 baskets[2] = 4。
  由於有一種水果未放置，我們返回 1。

示例 2

輸入： fruits = [3,6,1], baskets = [6,4,7]
輸出： 0
解釋：

• fruits[0] = 3 放入 baskets[0] = 6。
• fruits[1] = 6 無法放入 baskets[1] = 4（容量不足），但可以放入下一個可用的籃子 baskets[2] = 7。
• fruits[2] = 1 放入 baskets[1] = 4。
  由於所有水果都已成功放置，我們返回 0。

提示：

n == fruits.length == baskets.length
1 <= n <= 10^5
1 <= fruits[i], baskets[i] <= 10^9

分析：

線段樹本質上是一棵二叉樹。靈神的線段樹模版~ 貼在這裏：

// 模板來源 https://leetcode.cn/circle/discuss/mOr1u6/
// 線段樹有兩個下標，一個是線段樹節點的下標，另一個是線段樹維護的區間的下標
// 節點的下標：從 1 開始，如果你想改成從 0 開始，需要把左右兒子下標分別改成 node*2+1 和 node*2+2
// 區間的下標：從 0 開始
template<typename T>
class SegmentTree {
    // 注：也可以去掉 template<typename T>，改在這裏定義 T
    // using T = pair<int, int>;

    int n;
    vector<T> tree;

    // 合併兩個 val
    T merge_val(T a, T b) const {
        return max(a, b); // **根據題目修改**
    }

    // 合併左右兒子的 val 到當前節點的 val
    void maintain(int node) {
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    // 用 a 初始化線段樹
    // 時間複雜度 O(n)
    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) { // 葉子
            tree[node] = a[l]; // 初始化葉節點的值
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m); // 初始化左子樹
        build(a, node * 2 + 1, m + 1, r); // 初始化右子樹
        maintain(node);
    }

    void update(int node, int l, int r, int i, T val) {
        if (l == r) { // 葉子（到達目標）
            // 如果想直接替換的話，可以寫 tree[node] = val
            tree[node] = merge_val(tree[node], val);
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) { // i 在左子樹
            update(node * 2, l, m, i, val);
        } else { // i 在右子樹
            update(node * 2 + 1, m + 1, r, i, val);
        }
        maintain(node);
    }

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) { // 當前子樹完全在 [ql, qr] 內
            return tree[node];
        }
        int m = (l + r) / 2;
        if (qr <= m) { // [ql, qr] 在左子樹
            return query(node * 2, l, m, ql, qr);
        }
        if (ql > m) { // [ql, qr] 在右子樹
            return query(node * 2 + 1, m + 1, r, ql, qr);
        }
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }

public:
    // 線段樹維護一個長為 n 的數組（下標從 0 到 n-1），元素初始值為 init_val
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    // 線段樹維護數組 a
    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) {
        build(a, 1, 0, n - 1);
    }

    // 更新 a[i] 為 merge_val(a[i], val)
    // 時間複雜度 O(log n)
    void update(int i, T val) {
        update(1, 0, n - 1, i, val);
    }

    // 返回用 merge_val 合併所有 a[i] 的計算結果，其中 i 在閉區間 [ql, qr] 中
    // 時間複雜度 O(log n)
    T query(int ql, int qr) const {
        return query(1, 0, n - 1, ql, qr);
    }

    // 獲取 a[i] 的值
    // 時間複雜度 O(log n)
    T get(int i) const {
        return query(1, 0, n - 1, i, i);
    }
};

int main() {
    SegmentTree t(8, 0LL); // 如果這裏寫 0LL，那麼 SegmentTree 存儲的就是 long long 數據
    t.update(0, 1LL << 60);
    cout << t.query(0, 7) << endl;

    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    // 注意：如果要讓 SegmentTree 存儲 long long 數據，需要傳入 vector<long long>
    SegmentTree t2(nums); // 這裏 SegmentTree 存儲的是 int 數據
    cout << t2.query(0, 7) << endl;
    return 0;
}

作者：靈茶山艾府
鏈接：https://leetcode.cn/discuss/post/mOr1u6/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

本題我們從二分的角度來使用線段樹，即左子樹與右子樹的深度遞歸。

對於x = fruits[i]來説，我們二分的從 baskets中找到第一個大於等於x的籃子來裝水果，具體的：

• 如果整棵樹的最大值都比x小，説明當前沒有籃子可以裝的下x水果，直接返回-1，表示沒有滿足的下標；所以線段樹要維護區間最大值。
• 否則，遞歸左子樹（二分的左區間）；
• 如果左子樹沒有滿足條件的葉子結點，則遞歸右子樹（二分的右區間）；
• 如果最終有滿足條件的葉子結點，則將該葉子結點賦值為-1，表示已經使用，然後更新區間最大值，返回該葉子結點的下標。

二分結束後，如果返回值不是-1，説明找到了可以裝x水果的籃子，否則沒有符合條件的籃子，將最終結果加1。

AC代碼：

class SegmentTree {
    vector<int> mx;

    void maintain(int node) {
        mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
    }


    void build (const vector<int>& a, int node, int l, int r) {
        if (l == r) {
            mx[node] = a[l];
            return ;
        }

        int mid = (r - l) / 2 + l;
        build(a, node * 2, l, mid);
        build(a, node * 2 + 1, mid + 1, r);

        maintain(node);
    }

public:
    SegmentTree(const vector<int>& a) {
        size_t n = a.size();
        mx.resize(2 << bit_width(n - 1));
        build(a, 1, 0, n - 1);
    }

    // 找區間內第一個>=x 的數，並更新為-1，返回這個數的下標，沒有則返回-1
    int findFirstAndUpdate(int node, int l, int r, int x) {
        if (mx[node] < x) {
            return -1;
        }
        if (l == r) {
            mx[node] = -1;
            return l;
        }

        int mid = (r - l) / 2 + l;
        int i = findFirstAndUpdate(node * 2, l, mid, x);
        if (i == -1) {
            i = findFirstAndUpdate(node * 2 + 1, mid + 1, r, x);
        }

        maintain(node);

        return i;
    }

};

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        SegmentTree st(baskets);

        int ans = 0;
        int n = fruits.size();
        for (int f : fruits) {
            if (st.findFirstAndUpdate(1, 0, n - 1, f) == -1) {
                ans++;
            }
        }

        return ans;
    }
};