题目描述

机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N+1座建筑——从 0到 N编号，从左到右排列。编号为 0的建筑高度为 0个单位，编号为i的建筑高度为 H(i)个单位。起初，机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。如果 H(k+1)>E，那么机器人就失去H(k+1)−E的能量值，否则它将得到E−H(k+1)的能量值。游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式
第一行输入整数 N。

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

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

数据范围
1≤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

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
int q[N];
int n;
bool find(int u)
{
    for(int i=0;i<n;i++)
    {if(u<q[i])
    u=u-(q[i]-u);
    else u=u+(u-q[i]);
        if(u>1e5)//能量值肯定大于0，太大了缩小范围。如果能量值是100000，主函数会结束循环，
        //不管是不是最小能量值都会输出
        return true;
        if(u<0)//
        return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int  i=0;i<n;i++)
    scanf("%d",&q[i]);
    int l=0,r=1e5;//注意枚举的范围，这很重要，不是一定在数组中。
    while(l<r)
    {
    int mid=l+r>>1;
    if(find(mid)!=false)
    r=mid;//返回true，说明太大了，输出最小能量值。
    else l=mid+1;
    }
    printf("%d",l);

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla