[C++知识库]机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有?N+1N+1?座建筑——从?00?到?NN?编号，从左到右排列。

编号为?00?的建筑高度为?00?个单位，编号为?ii?的建筑高度为?H(i)H(i)?个单位。

起初，机器人在编号为?00?的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第?kk?个建筑，且它现在的能量值是?EE，下一步它将跳到第?k+1k+1?个建筑。

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

游戏目标是到达第?NN?个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数?NN。

第二行是?NN?个空格分隔的整数，H(1),H(2),…,H(N)H(1),H(2),…,H(N)?代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤1051≤N,H(i)≤105,

输入样例1：

5
3 4 3 2 4

输出样例1：

4

输入样例2：

3
4 4 4

输出样例2：

4

输入样例3：

3
1 6 4

输出样例3：

3

?代码如下

#include <iostream>

using namespace std;

const int N =1e5 +10;
int a[N];
int _max =0;
int n;

bool check(int e)//只要中间有一个大于_max；就成立
{
    for(int i =1;i <=n;i ++)
    {
        e =2 *e -a[i];//无论是第一种情况还是第二种都是一样的能量变化
        //动能重力势能相互转化；所以每一次的动，无论是上是下，都是单调递增
        //故用二分
    if(e >=_max) return true;
    if (e <0) return false ;//规律可得只要找到最大高度就为true
    }

}
int main ()
{
     cin>>n;
    for(int i =1;i <=n;i ++)
    {
        cin>>a[i];
        if(_max<a[i]) 
        _max =a[i];
    }
    int l =0 ,r = _max;
    while (r>l)
    {

        int mid =l +r>>1;
        if(check(mid)) r =mid; //二分
        else l =mid +1;
    }
    cout<<l;//r 也行
    return 0;
}