[蓝桥杯 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++ 代码

相关问题

完全二叉树的权值运行错误

完全二叉树的权值运行错误可能是由于代码中的错误导致的。根据引用和引用的代码，我注意到在两段代码中都使用了一个内部循环，该循环用于计算每个节点的权值，并将具有最大权值的节点的深度记录下来。然而，这两段代码存在一些错误和潜在的问题。

首先，引用中的代码在计算节点的深度时使用了对数函数，并在循环中累加每个节点的权值。但是，在这段代码中没有考虑到最后一层可能不是满的情况，因此可能导致计算的错误结果。

另外，引用中的代码在内部循环中使用了两个计数器count1和count2，并在每次循环中对它们进行了累加。然而，在每次循环中，只有当count2等于n时，内部循环才会提前结束。这可能导致在最后一层没有满的情况下，循环继续执行，从而出现错误。

为了解决这个问题，你可以在内部循环中添加一个判断条件，如果所有数字已经加完，则提前结束循环。这样可以避免在最后一层没有满的情况下导致的错误。

此外，你还可以检查其他可能的错误，例如数组越界、变量的初始化和更新等。

综上所述，完全二叉树的权值运行错误可能是由于代码中的错误导致的。你可以检查代码中的错误，并尝试修复它们以获得正确的结果。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [蓝桥杯2019年第十届真题——完全二叉树的权值](https://blog.csdn.net/Hello_world_n/article/details/122348243)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *3* [蓝桥杯试题 历届真题 完全二叉树的权值【第十届】【省赛】【B组】](https://blog.csdn.net/m0_51664084/article/details/124033204)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]

完全二叉树的权值c++

根据提供的引用[1]，以下是完全二叉树的权值C++代码的解释：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int que[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&que[i]);
    }
    long long num=2;//该层数字个数
    long long sum=0;//该层权数之和
    int du=1;//这是第几层
    int ji=1;//和最大的层数是多少
    int imax=que[1];//最大层的权值之和
    for(int i=2;i<=n;){
        sum=0;
        int j;
        du++;
        for(j=i;j<i+num&&j<=n;j++){
            sum+=que[j];
        }
        if(sum>imax){
            ji=du;
            imax=sum;
        }
        num*=2;
        i=j;
    }
    cout<<ji<<endl;
    return 0;
}

该代码的作用是计算完全二叉树的权值。具体来说，它首先读取输入的数字并将它们存储在一个数组中。然后，它计算每一层的权值之和，并找到权值之和最大的层数。最后，它输出最大权值的层数。