二分查找基本功练习！

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n, h[N];

bool check(const int e) { // e == energy 能量
  // 进行一遍递推检查
  int energy = e;
  for (int i = 1; i <= n; ++i) {
    energy = (energy << 1) - h[i];
    if (energy < 0) return false;
    if (energy > N) return true;
  }
  return true;
}

// binary search template:
// [l, r) 左闭右开区间
// Time Complexity: O(log(r - l) * (f(m + g(m))))
// Space Complexity: O(1)
int binary_search(int l, int r) {
  while (l < r) {
    // avoid integer overflow (避免整数溢出)
    int m = l + ((r - l) >> 1);
    if (check(m)) r = m; // [l, m)
    else l = m + 1; // [m + 1, r)
  }
  return l; // 返回最小的满足g(m) 这里就是check(m)函数条件的最小值
}

int main(void) {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
  printf("%d\n", binary_search(0, N));
}