[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≤N,H(i)≤1051≤N,H(i)≤10^51≤N,H(i)≤105

输入样例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;
}