题目描述

blablabla

算法1

(二分) $O(nlog(n))$

最关键的判断能量充足的条件，即再运动过程中 只要出现大于最大高度的能量 即表示能量充足，出现负能量则为能量不够的情况；
开始我是判断整个过程能量都大于0，这样肯定会数据溢出的，此处大坑 不能踩

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int height[N];

int main()
{
    int n;
    cin >> n;
    int max_height = 0;
    for(int i = 0; i < n; i++)
        cin >> height[i], max_height = max(max_height, height[i]);
    int l = 1, r = max_height;
    while(l < r)
    {
        int mid = l + r >> 1;
        long long en = mid;
        bool flag = true;
        for(int i = 0; i < n; i++)
        {
            if(height[i] > en)
                en -= height[i] - en;
            else
                en += en - height[i];
            //if(mid == 75) cout << en << endl;
            if(en < 0)
            {
                flag = false;
                break;
            }
            else if(en > max_height)
                break;
        }
        //cout << l << " " << r << endl;
        if(!flag) l = mid+1;
        else r = mid;
    }
    cout << l << endl;
    return 0;
}

```