题解 | #机器人跳跃问题#

注意E在每一层的值不一定相同，定义在k个建筑时，能量为E_k，可依次递推出等式

E₁ = 2E₀ - H₁ ≥ 0
E₂ = 2E₁ - H₂ = 4E₀ - 2H₁ - H₂ ≥ 0
···
E_k = 2E_k-1 - H_k ≥ 0

每个E_k值均大于0，每个等式均可以得到关于E₀的一个下限，取下限的最大值，即为答案。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int N, E = 0, tmp;
    long long sum = 0;	//用来记录等式中相应H多项式的求和
    double i = 2.0;		//不等式中E的系数
    cin >> N;
    while(N--) {
        cin >> tmp;
        sum = sum*2 + tmp;
        E = max(E, (int)ceil(sum/i));
        i *= 2;
    }
    cout << E;
    return 0;
}