思路:在1~10000点能量中二分出到达第N座建筑需要的最小能量值。因为建筑物高度上限是10000,只要机器人初始能量大于等于10000,那么过程中它的能量就肯定不会减少,所以10000点能量是上限。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N];
bool check(int e) //判断机器人初始能量为e时能否到达N号建筑
{
for (int i = 1; i <= n; i ++ )
{
e = e * 2 - h[i];
if (e >= 1e5) return true; //e只要大于1e5,之后就只会增加不会减少了,故返回true
if (e < 0) return false; //同理,e只要小于0就只会减少不会增加了,故返回false
}
return true;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> h[i];
int l = 0, r = 1e5; //经典二分模板
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}