算法1 二分

1. 初始能量越大，能通过的可能性自然越大，当初始能量等于$h[i]_{max}$，那么必不存在能量减少的情况，即必然通过 （因此具有单调性，可以考虑二分）
2. 直接枚举所有可能的答案，时间复杂度$O(n^2)=O(10^{10})$，二分$O(nlogn)$
3. 主要是注意中间递推模拟时，边界条件的设置（与下界、上界对比）

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = (int) 1e5 + 10;
    static int[] h = new int[N];

    static boolean check(int e) {
        for (int i = 0; i < n; i++) {
            e += e - h[i + 1];
            if (e < 0) return false;  // 小于0则失败
            else if (e > N) return true;  // 大于极大值（或max(h[i])）必能通过 不截断会累加到溢出
        }
        return true;
    }

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) h[i] = scanner.nextInt();
        int l = 0, r = N;  // 左界0 右界极大值 也可以是max(h[i]) 
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (check(r)) System.out.println(r);
    }
}

算法2 贪心逆推

1. 观察算法1代码，递推过程使用e += e - h[i+1]，即$e_{i+1} = 2e_i - h_{i+1} \Longrightarrow e_i=\frac{e_{i+1}\ \ + \ h_{i+1}}{2}$，所以从当前的$e$和$h$可以逆推出前一个$e$
2. 待求的值为$e_0$，只需从末态$e_n$反推到$e_0=\frac {e_1+h_1}2$，因为没有$h_{n+1}$所以末态$e_n$需要我们指定
3. 最好的情况应该是“通过最后一个$h$时能量恰好为0”（但也存在无法为0的情况，比如建筑物只有一个且值为1，此时最优解为1，末态能量为2）
   • 假设$e_n=0$，则$e_n = 2e_{n-1}-h_n \Longrightarrow e_n+h_n=2e_{n-1}$，注意等号右边显然为偶数，但是左边有可能是奇数
   • 当左边为奇数时，说明我们设置的$e_n$是无法达成的，为了满足递推关系，需要将左边补为偶数，即+1
   • 所以当$e_n+h_n$为奇数时，$e_{n-1}=\frac{e_n+h_n+1}{2}$

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = (int) 1e5 + 10;
    static int[] h = new int[N];

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) h[i] = scanner.nextInt();
        int e = 0;
        for (int i = n; i >= 1; i--) {
            e += h[i];
            if ((e & 1) == 1) e++;
            e >>= 1;
        }
        System.out.println(e);
    }
}