题目描述

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值

得到式子
$E’=2E-H(k+1)$
因为失去$H(k+1)−E$和得到$E−H(k+1)$都是$E+=E−H(k+1)$

其次
当$E’>=0, $ $E’=2E-H(k+1)>=0$
即$E=H(k+1)/2>=0$
意思是后一个$E>=0$，前面的都$E>=0$
这样只要保证最后一个不小于0就行了
而题目要我们求临界条件“至少”，就令其最后的能力值$E=0$
因为能量值更大的话，只会更难变为负数：

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值

然后通过倒推的方式求解，注意结果向上取整

时间复杂度$O(n)$

C++ 代码

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
double H[MAXN];
int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {

        for(int i=1;i<=n;i++)
        scanf("%lf",&H[i]);
        double E=0;
        for(int i=n;i>=1;i--)
        E=(E+H[i])/2;

        printf("%d\n",(int)ceil(E));
    }
    return 0;
}