AcWing 730. 机器人跳跃问题
原题链接
中等
作者:
晴天.
,
2023-03-22 22:07:30
,
所有人可见
,
阅读 173
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int h[N];
bool check(int e)
{
for(int i=1;i<=n;i++)
{
e=e*2-h[i];
if(e<0)return false;
if(e>1e5)return true;//根据条件公式2*e-h[i] h[i]最大1e5,但e>1e5时可只后续遍历条件都满足提前退出,进入下一个mid点
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&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;
return 0;
}