[Daimayuan]Lusir的游戏（C++，搜索）

$Lusir$ 正在玩一个古老的基于 $DOS$ 的游戏。

游戏中有 $N+1$ 座建筑——从 $0$ 到 $N$ 编号，从左到右排列。编号为 $0$ 的建筑高度为 $0$ 个单位，编号为 $i$ 的建筑高度为 $H(i)$ 个单位。 起初，$Lusir$ 在编号为 $0$ 的建筑处。每一步，它跳到下一个（右边）建筑。假设 $Lusir$ 在第 $k$ 个建筑，且它现在的能量值是 $E$，下一步它将跳到第 $k+1$ 个建筑。

如果 $H(k+1)>E$，那么 $Lusir$ 就失去 $H(k+1)-E$ 的能量值，否则他将得到 $E-H(k+1)$ 的能量值。

游戏目标是到达第 $N$ 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是 $Lusir$ 至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 $N$。 第二行是 $N$ 个空格分隔的整数，$H(1),H(2),\dots ,H(N)$ 代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

$1\le N,H(i)\le 10^5$

输入样例1：

5
3 4 3 2 4

输出样例1：

4

解题思路

答案具有单调性：能量越多，我们成功通关的可能性越大

所以采用二分搜索答案，如果能够成功通关，我们去中点左侧搜索，如果不能，我们去中点右侧搜索

至于如何判断，采用模拟即可

*注：模拟时需要注意一点，当能量过高时，之后的能量可能会以指数形式增长，导致直接爆long long造成判断异常。这里简单加上一个判断条件：如果当前能量大于或等于最高的建筑，我们就可以判断能够通关，因为之后的能量只可能增不会减

AC代码如下

#include <iostream>
using namespace std;
const int max_n = 1e5;
const int max_h = 1e5;

int buildings[max_n + 1], n, max_value = -1;


bool judge(long long e) {
	for (int i = 1; i <= n; i++) {
		e += e - buildings[i];
		if (e < 0) return false;
		if (e >= max_value) return true;
	}
	return true;
}


int bin_search() {
	int l = -1, r = max_value + 1;
	while (l + 1 != r) {
		int m = (l + r) / 2;
		if (judge(m)) r = m;
		else l = m;
	}
	return r;
}


int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> buildings[i];
		max_value = max(max_value, buildings[i]);
	}
	cout << bin_search() << endl;
	return 0;
}