[蓝桥杯 2019 省 AB] 完全二叉树的权值

题目描述

给定一棵非空完全二叉树，树中每个节点都有一个权值，按照层序遍历的顺序依次将每个节点的权值存储到一个一维整型数组中，数组下标从1开始。现在，给定数组下标k和一个整数K，要求计算出以k为根节点的子树中权值不大于K的节点个数。

输入格式

第一行包含两个整数n和K，分别表示数组长度和权值上限。

第二行包含n个整数，其中第i个整数表示下标为i的节点的权值。

第三行包含两个整数k和K，表示待查询的子树以及权值上限。

输出格式

输出一个整数，表示满足条件的节点个数。

数据范围

1≤n≤100000,
1≤K≤10000,
1≤节点权值≤10000

样例

输入样例：

15 8
2 3 5 6 7 8 9 1 3 6 7 8 9 3 2
3 8

输出样例：

3

算法1

(暴力枚举) $O(n^2)$

暴力枚举每个子树中权值不大于K的节点个数

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码