二分 机器人的跳跃问题

二段性:找到一个值，大于此值的时候都成立，小于的时候都不成立

更新的方式只有两种，左边的mid更新不需要+1；右边的mid更新需要+1

---

//对能量进行二分，确定能量的范围
//特判防止溢出int
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
int a[N],n;bool check (int e)
{for(int i=1;i<=n;i++){e=2*e-a[i];//更新能量if(e>=1e5)return true;if(e<0) return false;}return true; 
}int main()
{cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);//对能量进行二分//确定能量的范围//当当前能量大于最大的能量的时候一定可以满足条件int l=0,r=1e5;while(l<r){int mid=l+r>>1;//当前能量满足，满足条件的最小值在当前mid的左边，所以r=mid//l=mid+1,mid=l+r>>1;//else l=mid+1 对对应的mid不需要+1//找到满足条件的最小值if(check(mid)) r=mid;else l=mid+1;}printf("%d",l);return 0;
}