欢迎关注

分析

y总刚刚讲的二分，所以本蒟蒻就使用二分实现啦,左右边界分别是$l=0，r=maxH$。题目说如果$H(k+1)>E$，那么机器人就失去$H(k+1)-E$的能量值，否则它将得到$E-H(k+1)$的能量值，那我们就可以写一个$success$函数，其中判断条件就是任何一步的能量值都不能小于$0$，如果小于$0$就返回$false$，如果其中有任何一步使得能量大于最大高度返回$true$,否则就返回$false$。

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int maxH = -1;
int h[100005];
bool success(int x)
{
    int temp = x;
    for (int i = 1; i <= n; i++)
    {
        temp += temp - h[i];
        if (temp < 0) return false;
        if (temp >= maxH) return true;
    }
    return true;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &h[i]);
        maxH = max(maxH, h[i]);
    }
    int l = 0, r = maxH;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (success(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    } 
    printf("%d\n", l);
    return 0;
}