蓝桥杯刷题冲刺 | 倒计时25天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.完全二叉树

• 题目

  链接： 完全二叉树的权值 - 蓝桥云课 (lanqiao.cn)

  给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅A N，如下图所示：

  

  现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。

  注：根的深度是 1。

  输入描述

  第一行包含一个整数 N*（1≤N≤105）。

  第二行包含 N 个整数A1,A2,⋅⋅⋅A**N*（−$10^5$ ≤A i≤$10^5$ ）。

  输出描述

  输出一个整数代表答案。

  输入

  7
  1 6 5 4 3 2 1
  

  输出

  2
  

• 题解

  #include<bits/stdc++.h>
  using namespace std;const int N=1e5+10;
  int a[N];  //数组的大小 开的大一点 int main()
  {int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int depth=0;long long sum=-1e18;  //让 sum 尽可能的小，因为输入的数中含有负数  //我们可以举几个例子，推出规律 //每一层的一个数编号为 2^(i-1) ,每一层的的个数为 2^(depth-1) for(int i=1,d=1;i<=n;i*=2,d++)  // i 表示，每一层的第一个编号{	long long s=0;  //每一层的 权值 for(int j=i;j<i+(1<<d-1)&&j<=n;j++)  //j 表示每一层的编号，保证 j 不越每一层的界和整个节点个数的界 s+=a[j];if(sum<s)  //比较每一层 权值 {sum=s;depth=d;	}	} cout<<depth;return 0;
  }
  

• 反思

  读题，理解他深层次的要求，明确要求什么

  属于一个规律题，编号可以 推出来

  逻辑一定要 正确，思路清晰一点，数据范围的处理