AcWing 730. 机器人跳跃问题
原题链接
中等
作者:
ZhangQ
,
2022-02-28 20:46:57
,
所有人可见
,
阅读 135
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int h[N];
int n;
bool check(int e)
{
for(int i=1;i<=n;i++)
{
e = 2*e - h[i];
if(e>N) return true; //如果当前的值大于了最大,根据性质后边均大于0.
if(e<0) return false;//小于零说明当前值不满足。
}
return true;
}
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i ++ ) scanf("%d",&h[i]);
int l=0,r = N; //右边界先取最大值。
int mid;
while(l<r)
{
mid = l + r>>1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d",l);
return 0;
}