O(n) 从后往前递推一遍

根据题目, 我们得到的公式是: $E’ = 2E - H(k+1)$

先假设到达最后是0能量, 然后往前推: $E = \frac{E’ + H(k+1)}{2}$ , 将结果储存在res[]数组中

保留计算得到小数, 直到第0位置

判断 res[0] 是否 是一个整数:

• 如果是, 即为答案, 输出
• 如果不是, 向上取整, 输出

#include<iostream>
#include<cstdio>
#define N 100010
#define EOF 1e-5
using namespace std;

int n;
int h[N];
double res[N];

int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        scanf("%d", &h[i]);
    for(int i=n-1; i>=0; i--){
        res[i] = (res[i+1] + h[i+1]) / 2;
    }
    if(res[0]-(int)res[0]>EOF){
        cout<<(int)res[0]+1;
    }else{
        cout<<(int)res[0];
    }
    return 0;
}