蓝桥杯试题 历届真题 完全二叉树的权值【第十届】【省赛】【B组】

Question

#include<stdio.h>
#include<math.h>
long long n;
long long a[1000000];
long long t[100000];
long long sum=0;
long long mark=0;

int main(){
    long long i=0,j;
    long long x=-1;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    /*
    n++;
    while(n){
        n=(long long)n/2;
        x++;
    }
    过不去 
    */ 
    /*
    x=0;
    while(n){
        n=(long long)n/2;
        x++;
    }
    过得去 
    */ 
   // x=ceil(log(n+1)/log(2));过得去 
    t[1]=2;
    for(i=2;i<=x;i++)t[i]=t[i-1]*2;
    j=1;
    for(i=1;i<=x;i++){
        long long middle=0;
        for(j;j<=t[i]-1;j++){
            middle+=a[j];            
        }    
        if(middle>sum){
            mark=i;
            sum=middle;
        }
        
    }
    printf("%lld",mark);
    
}

判断深度那一段第一种方法为什么过不去，有什么问题吗，实在是整不明白.

Answer 1

你x求得应该是树得深度。
你第一个方法，初始化的x=-1，拿个n=2试试，结果x=1。但是如果让x=0，拿n=7试试得时候，又会得到x=4的结果。所以问题可能不在于x取多少。
我觉得你是想用2^x>=n+1来求，有两个思路一个是看乘多少2刚好大于等于n+1，另一个则是你这种。其实问题关键在于n/2是向下取整的，意味着你每次奇数除以2都会损失一部分，当没有损失的时候你能够在x=0求出正确答案。