二分问题

答案一定在1到100000之间，即在a[i]的范围之内
证明：
想要使答案最大，那么就一定需要a[i]取最大值10^5，此时取值ans为10^5
刚好可以完美通过该序列，在取值>10^5的数也可以通过，即10^5为答案的上确界
从1开始二分，很容易看出来下界为1

在cheek函数中当取的curans>=序列的最大值时，该anscur>=ans,就可以直接break掉，防止爆int
出现curans<0的情况说明该答案curans < ans ,返回false即可

动态记录一下最大值maxv(o(n))即可，也可以使用RMQ算法求解(o(log2(n))) (但是没必要)

该题的整体时间复杂度：
二分答案n * log2(10^5)
15 > log2(10^5) < 20
最终时间复杂度：o(n)

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] a = new int[N];
    static int n, maxv;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());

        String[] s = sc.nextLine().split(" ");

        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
            maxv = Math.max(maxv, a[i]);
        }

        int l = 1, r = 100000;
        while (l < r) {
            int mid = l + r >> 1;
            if (cheek(mid)) r = mid;
            else l = mid + 1;
        }

        System.out.println(r);
    }

    /**
    * 根据题目要求写即可
    */
    static boolean cheek(int ans) {
        for (int i = 0; i < n; i++) {
            if (a[i] > ans) ans -= a[i] - ans;
            else ans += ans - a[i];
            if (ans >= maxv) return true;
            if (ans < 0) return false;
        }

        return true;
    }
}