730. 机器人跳跃问题--二分
题目：
730. 机器人跳跃问题 - AcWing题库
思路： 二分
1.当起始能量E大于最大建筑高度1e5 时，E的能量在整个条约过程中全程递增，则大于E的初始能量也必然成立（满足二段性）。故最小初始能量范围为[0,1e5]（确定了二分范围）。
2.满足二分条件，可用二分！！！
代码：
//二分
/*二段性：当起始能量E满足机器人跳跃过程E!=0的条件时，
比初始值E大的值也必然成立*/
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int h[N],n;
bool check(int e)
{
for(int i=1;i<=n;i++){//遍历机器人到达每座建筑上的能量E
e=2*e-h[i];
if(e<0)return false;//在到达最后的第n座建筑前<=0,必然会出现负，说明e取小了
if(e>=1e5)return true;//如果到达某座建筑上时的能量大于等于建筑高度最大值，
//那机器人在后面的跳跃过程中必然是递增的，不可能为0
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
int L=1,R=1e5;
while(L<R){
int mid=L+R>>1;//二分
if(check(mid))R=mid;
else L=mid+1;
}
cout<<L;
}