题目链接：点击这里
思路：
当 H ( k + 1 ) > E H(k+1) > E H(k+1)>E 时，机器人就失去 H ( k + 1 ) − E H(k+1) - E H(k+1)−E 的能量值，即 E − ( H ( k + 1 ) − E ) = 2 E − H ( k + 1 ) E-(H(k+1)-E) = 2E-H(k+1) E−(H(k+1)−E)=2E−H(k+1)
否则，将得到 E − H ( k + 1 ) E - H(k+1) E−H(k+1) 的能量值，即 E + ( E − H ( k + 1 ) ) = 2 E − H ( k + 1 ) E+(E-H(k+1)) = 2E-H(k+1) E+(E−H(k+1))=2E−H(k+1)
一个直观感觉，初始能量越大就越能完成游戏，用数学归纳法可以证明初始能量具有单调性。因此，我们可以对初始能量进行二分去寻找答案。
在check()函数中，如果我们仅仅依靠上述公式去递推判断，是会爆掉 int 和 long long 的，因为能量值是呈 2 2 2 的指数级增长的。
比较巧妙的地方是，可以挖掘出下面这一条性质去提前结束循环防止溢出。
对于某个当前能量值 E ( E ≥ m a x H ) E\ (E \geq maxH) E (E≥maxH)，那么它下一点的能量值为 2 E − H ( i ) = E + E − H ( i ) ≥ E 2E-H(i) = E+E-H(i) \geq E 2E−H(i)=E+E−H(i)≥E。
得出结论：如果某个能量值已经大于等于 m a x H maxH maxH 了，那么它后面的能量值都是递增的，不会有减少的了。故有了该性质，就不用去挨个循环递推了。
AC代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100010; int n; int h[N]; bool check(int e) { for(int i = 1; i <= n; i++) { e = 2 * e - h[i]; if(e >= 1e5) return true; if(e < 0) return false; } return true; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &h[i]); int l = 0, r = 1e5; while(l < r) { int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid + 1; } printf("%d\n", r); return 0; }