算法分析

• 1、由题意可知，在枚举每个塔的高度的过程中，一旦出现超过所有塔的最高值MaxVal时，能量只增不减，一定可行

• 2、在[0,MaxVal]值域中，通过二分找到能保证中途不出现0且最大的值

• 3、check()函数表示，该x值是否能够在通过所有塔时，能量值不出现0，若能则返回true，否则返回false

时间复杂度 $O(nlogn)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int n;
    static int[] h = new int[N];
    static int maxVal = Integer.MIN_VALUE;
    //若遍历所有
    public static boolean check(int x)
    {
        long res = x;
        for(int i = 1;i <= n;i++)
        {
            if(h[i] > res) res -= (h[i] - res);
            else res += (res - h[i]);
            if(res < 0) return false;
            if(res > maxVal) return true;
        }
        return true;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++)
        {
            h[i] = Integer.parseInt(s1[i - 1]);
            maxVal = Math.max(maxVal, h[i]);
        }
        int l = 0,r = maxVal;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.println(l);

    }
}