why

求最小/最大都第一时间想到二分（二分- dfs - dp - 贪心），具有“单调性“的题目都可以用二分来做，那我们考证一下E0‘>E0，E0可以完成任务，E0‘是否也可以成功完成，如果是那么它就是一个单调递增的。经过下图分析，很明显这道题是训练二分的一道好题。
image.png

how

读题

  • 有i个城堡，城堡高度从0 ～ i排布（从低到高）
  • 机器人从0开始不断跳跃，而且机器人存在能量值E，跳跃会消耗机器人的能量
  • 如果城堡高度H（i+1）> E ，损失H - E，否则 增加E-H（也就是机器人往比它能量高的城堡高度条，会损失能量。往比它能量低的城堡跳会获得能量，计算公式就是大 减去小）

问：需要多少能量机器人才能跳完所有城堡
ps:经过数据转换得到一个公式，2E-h。
image.png

思路

1.取一个相对大的范围，暴力夹击（每次取中间值，然后将暴力区域不断划分到数组左右两边）,每轮的中间值都拿去跑所有塔。
2.只要机器人不死就是true，死了（E<0）false，
3.还有一种溢出情况需要考虑，如果这个中间值非常大了，在跑塔过程中可能会爆掉int内存，既然它能量非常大了也没必要进行跑塔了，直接让它通过。

代码

  1. import java.util.Scanner;
  3. public class robot {
  4.     static int[] nums;
  6.     public static boolean check(int e) {
  7.         for (int i = 0; i < nums.length; i++) {
  8.             e = 2 * e - nums[i];
  9.             if (e >= 100010) {
  10.                 return true;
  11.             }
  12.             if (e < 0) {
  13.                 return false;
  14.             }
  15.         }
  16.         return true;
  17.     }
  19.     public static void main(String[] args) {
  20.         Scanner sc = new Scanner(System.in);
  21.         int numsLength = sc.nextInt();
  22.         nums = new int[numsLength];
  23.         for (int i = 0; i < numsLength; i++) {
  24.             nums[i] = sc.nextInt();
  25.         }
  26.         int left = 0;
  27.         int right = 100010;
  28.         while (left < right) {
  29.             int middle = (left + right) / 2;
  30.             if (check(middle)) {
  31.                 right = middle;
  32.             }else{
  33.                 left = middle+1;
  34.             }
  35.         }
  36.         System.out.println(left);
  37.     }
  38. }