P5076 【深基16.例7】普通二叉树（简化版）题解

shensiyuan2011 · 2024-04-27 14:02:46 · 题解

思路

拿到题目的好习惯，偷看一眼标签：
模拟！！
nice！接下来我们考虑用啥模拟。
看到“排名”“前驱”“后驱”这些词，以及本题的数据保证插入前 𝑥 不在集合中(就是没有重复的元素)，我们应该可以想到c++自带的STL:

set<int>a;

于是，我们用set模拟就可以了。
不知道set的点这里

代码

本人代码丑，不喜勿喷。

#include <bits/stdc++.h>
using namespace std;
set<int>a;
int n;

int mian() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int q;
    cin >> q;
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {  //暴力求排名
            int cnt = 1;
            for (auto i : a) {
                if (i >= x)
                    break;
                cnt++;
            }
            cout << cnt << '\n';
        } else if (op == 2) {  //暴力查排名为x的元素
            int cnt = 1;
            for (auto i : a) {
                if (cnt == x) {
                    cout << i << '\n';
                    break;
                }
                cnt++;
            }
        } else if (op == 3) {  //二分求前驱
            auto it = a.lower_bound(x);
            if (it != a.begin())
                cout << *prev(it) << '\n';
            else
                cout << -2147483647 << '\n';
        } else if (op == 4) {  //二分求后驱
            auto it = a.upper_bound(x);
            if (it != a.end())
                cout << *it << '\n';
            else
                cout << 2147483647 << '\n';
        } else  //插入
            a.insert(x);
    }
    return 0;
}

注意：请勿直接复制