Catshao

用户名：Catshao

访问量：28829

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

蓝桥杯2020年第十一届省赛真题-BST插入节点问题

　　作者: Catshao　　　　发表时间：2022-02-10 20:18:28 浏览：547　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-BST插入节点问题

~~editor.md 太阴间，编辑公式体验极差~~

原题 $$N \le 1000$$ ，被我给加强了。

暴力我也不会，就直接讲（疑似正解）吧。

我是照着这个思路造的数据，如果错了请及时告诉我。

### 100pts

这道题的查询可以转换为前驱后继的差 - 1 。

很容易得知结点 $$K$$ 是否有左子结点和右子结点。

先对 $$W$$ 排个序记为 $$W'$$ ，并找到 $$W\_k$$ 在 $$W'$$ 中的位置，记为 $$k'$$。如果 $$K$$ 没有左子结点，那么 $$x$$ 可以在 $$(W\_{k\text{的前驱}}, W\_k)$$ 内取值（$$(l, r)$$ 是开区间的意思，意思是不包含区间两头 $$l, r$$ 的区间） 。$$W\_{k\text{的前驱}}$$ 也就是 $$W'\_{k' - 1}$$ 。知道了这些后就可以算出 $$x$$ 插入进树后为结点 $$K$$ 的左结点有多少种取值。右结点对应后继，计算方式大同小异。

由于此题 $$K$$ 只有一个，因此不需要排序也能找出 $$W\_{k\text{的前驱}}$$ 和 $$W\_{k\text{的后继}}$$ 。用了排序时间复杂度为 $$O(n \log n)$$ ，没用排序时间复杂度为 $$O(n)$$ 。

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

const int MAX_N = 1000100;

int n, k, p[MAX_N], a[MAX_N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> a[i];
    }
    bool l = true, r = true;
    for (int i = 1; i <= n; ++i) {
        if (p[i] == k) {
            if (a[i] < a[k]) {
                l = false;
            } else {
                r = false;
            }
        }
    }
    int temp = a[k];
    sort(a + 1, a + n + 1);
    k = lower_bound(a + 1, a + n + 1, temp) - a;
    if (k == 1 || k == n) {
        cout << 1 << endl;
    } else {
        cout << (l ? a[k] - a[k - 1] - 1 : 0) + (r ? a[k + 1] - a[k] - 1 : 0) << endl;
    }
    return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (II) （C语言代码）

蓝桥杯2020年第十一届省赛真题-BST插入节点问题

评论区

精彩推荐

数列（C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

wu-理财计划（C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (II) （C语言代码）

蓝桥杯2020年第十一届省赛真题-BST插入节点问题

评论区

精彩推荐

数列 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

wu-理财计划 （C++代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

　　评论区

数列（C++代码）

wu-理财计划（C++代码）

求圆的面积（C语言代码）