归纳推导

递推关系: E(i+1) = 2xE(i) - h[i+1];

即:
E1 = 2 x E0 - h1;
E2 = 2 x E1 - h2 = 4 x E0 - 2 x h1 - h2;
E3 = 2 x E2 - h3 = 8 x E0 - 4 x h1 - 2 x h2 - 4 x h3;
......

可得到通项:

Ei = 2^i x E0 - 2^(i-1) x h1 - 2^(i-2) x h2 - 2^(i-3) x h3 … - 2^(0) x hi;

对于任意一项满足Ei >= 0, 即

2^i x E0 - 2^(i-1) x h1 - 2^(i-2) x h2 - 2^(i-3) x h3 … - 2^(0)hi >= 0;

E0 >= h1/2 + h2/(2^2) + h3/(2^3) … - hi/(2^i);

所有不等式中,当i等于n时右边最大,那么E0的最小值为:

h1/2 + h2/(2^2) + h3/(2^3) … - hn/(2^n);

时间复杂度为:O(n)

java 代码

import java.util.Scanner;

class Main{
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int []h = new int[n];
        double res = 0;
        for(int i = 0; i < n; i++){
            h[i] = scan.nextInt();
        }

        for(int i = n-1; i >= 0; i--){
            res = (res + h[i])/2.0;
        }
        System.out.println((int)Math.ceil(res));
    }
}