官方题解｜照片装裱

题目解析

我们可以把所有的照片和相框的宽度和长度放在一块，并按照宽度从大到小排序，如果一个照片和一个相框的宽度相同，则将相框放在前面。

接下来准备一个容器 $S$，并遍历排序后的照片和相框：

• 若当前为相框 $(C_i, D_i)$，则将 $D_i$ 放入 $S$ 中。
• 若当前为照片 $(A_i, B_i)$，则从 $S$ 中找最小的大于等于 $B_i$ 的元素，并将其从 $S$ 中删除。如果无法找到这样的元素，说明这个照片无法找到一个相框来装裱，答案为 $\tt{No}$。

如果成功遍历完所有的元素，答案为 $\tt{Yes}$。

如果使用一个普通数组充当容器 $S$，那么以上算法的时间复杂度为 $O(NM)$，但是我们可以使用 std::multiset 作为 $S$ 来解决这个问题，时间复杂度为： $O((N + M)\log{(N + M)})$。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> a(n), b(m);
        for (auto &[w, l] : a) cin >> w;
        for (auto &[w, l] : a) cin >> l;
        for (auto &[w, l] : b) cin >> w;
        for (auto &[w, l] : b) cin >> l;
        vector<tuple<int, bool, int>> arr;
        for (auto &[w, l] : a)
            arr.emplace_back(w, 0, l);
        for (auto &[w, l] : b)
            arr.emplace_back(w, 1, l);
        sort(arr.rbegin(), arr.rend());
        auto check = [&]() {
            multiset<int> st;
            for (auto &[w, t, l] : arr) {
                if (t) st.insert(l);
                else {
                    auto obj = st.lower_bound(l);
                    if (obj == end(st)) return false;
                    st.erase(obj);
                }
            }
            return true;
        };
        cout << (check() ? "Yes" : "No") << '\n';
    }
    return 0;
}

---