分析

• 第i层的个数总共有2^(i-1),假定最后一层有100010个，求出最大层数为17,有公式log2(x)=log(x)/log(2)

• 要注意求和结果为负数，保留最小和时要初始化为负无穷。

C++ 代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

#define ffor(i,begin,end) for(int i=(begin);i<(end);++i)//[begin,end)

#define out(x) cout<<x<<" "
#define nl cout<<endl

typedef long long LL;

const int INF = 1e9;
const int MAXN = 100010;


//var
int gn;
int a[MAXN];

LL gsum=-INF;//最大和,陷阱
int Depth=1;//层数

//fun

void init(){
    cin>>gn;
    gn++;//不用0位置
    ffor(i,1,gn){
        scanf("%d",&a[i]);
    }
}


LL cal(int s,int e){
    LL sum=0;

    if(s>=gn){
        return -INF;
    }

    if(s<gn){
        if(e>gn){
            ffor(k,s,gn){
                sum+=a[k];
            }
        }else{
            ffor(k,s,e){
                sum+=a[k];
            }
        }
    }

    return sum;
}


void AcWing(){
    init();
    ffor(d,1,20){
        //[s,e)
        int s=pow(2,d-1);
        int e=(s<<1);

        LL tmpSum=cal(s,e);
        if(tmpSum>gsum){
            Depth=d;
            gsum=tmpSum;
        }

    }
    out(Depth);nl;
}


int main()
{
//  init();
//  int s=pow(2,3-1);
//  int e=(s<<1);

//  out(s);out(e);nl;
//  out(cal(s,e));

    AcWing();
    return 0;
}