AcWing
730. 机器人跳跃问题
二分：初始的能量值对模拟的结果具有二段性，即当$e\ge e_{min}$，可以成功完成游戏；否则不能成功完成游戏。此处$e_{min}$即为要输出的结果。所以可以使用二分搜索这个结果(0~maxe，其中maxe是最高的建筑的高度)，对于每次迭代，模拟机器人跳跃的整个过程，如果过程中出现能量为负值，就返回false；如果过程中出现能量>=maxe，那么返回true. 需要注意不要等整个模拟结束，没有发现负值，才返回true，因为能量值的叠加会导致爆int.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int h[N];
int maxe = -1;
bool check(int e){
for(int i = 1; i <= n; i++){
if(h[i] > e){
e -= (h[i] - e);
if(e < 0) return false;
}
else{
e += (e - h[i]);
if(e > maxe) return true; // 如果确定了可以，就提前返回，否则一直加，会爆int
}
}
return true;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> h[i];
if(h[i] > maxe) maxe = h[i];
}
int l = 0, r = maxe;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r;
}
贪心：从后往前递推。对于最后一步，需要满足e1 + (e1 - h[n]) >= 0，此时求出到最后一步之前所需要的最小的能量e1，那么就至少要保证，其再上一步到这一步之后，能量>=e1，也就是e2 + (e2 - h[n-1]) >= e1，如此递推，直到推出第一步之前所需要的最小能量，即为题解。
递推的公式是：$e_k \ge \lceil \frac{e_{k+1} + h[k+1]}{2} \rceil ,\quad 0 \le k \le n-1$.
四舍五入使用round()函数。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int h[N];
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
int e = 0;
for(int i = n; i >= 1; i--) e = round((double)(e + h[i]) / 2);
cout << e;
return 0;
}