AcWing 1240. 完全二叉树的权值（双指针）

AcWing 1240. 完全二叉树的权值

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

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A₁,A₂,???A_N。

输出格式
输出一个整数代表答案。

数据范围
1≤N≤10⁵,
?10⁵≤A_i≤10⁵
输入样例：

7
1 6 5 4 3 2 1

输出样例：

2

题目分析

双指针，模拟深度的左端点和右端点
记住要开 long long，会爆 int
注意在内层循环中不能数组越界

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>#define x first
#define y secondusing namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 101000;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;int n; 
ll a[N];int main()
{
    cin >> n;for(int i = 0; i < n; i ++ ) cin >> a[i];ll sum = 0;int maxx = -INF, flag = -1, idx = 1;for(int i = 0, j = 1; i < n; i ++ ){
    for(i; i < j && i < n; i ++ ) sum += a[i];if(sum > maxx){
    maxx = sum;flag = idx;}sum = 0;j += pow(2, idx);idx ++ ;i -- ;}cout << flag << endl;return 0;
}