题目描述

机器人正在玩一个古老的基于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) ≤ 10^5
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

(逆推法)

根据题意:
当前能量大于 H(i)时，E(i) = E(i - 1) + E(i - 1) - H(i),即E(i - 1) = (E(i) + H(i)) / 2
当前能量小于 H(i)时, E(i) = E(i - 1) - (H(i) - E(i - 1)), 即 E(i - 1) = (E(i) + H(i)) / 2
由此可以从最后一个状态逆推出第一个状态
值得注意的是:中间过程可能出现(E(i) + H(i)) / 2有余数,须向上取整,因为向下取整,会导致过程中出现负能量的情况

时间复杂度 O(n)

参考文献

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6;
int h[N];
int main(){
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    int t = 0,res;
    //假设走完后能量为0(实际上可能不为0),逆推走完前一个后剩下的能量
    for(int i = n - 1; i>= 0; i--){
        res = ceil((h[i]+t)/2.0);
        t = res;
    }
    cout << res << endl;
    return 0;
}