AcWing 730. 机器人跳跃问题
原题链接
中等
作者:
ofs
,
2024-04-11 23:44:28
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
//记录建筑信息,放在开头作为全局变量,容易修改
const int N=1e5+10;//一定要加const 并且从一开始就使用数据的最大值设定数组
int a[N];//同时设定一个最大的数组
int n;
bool h(int e)
{
int i;
for(i=0;i<n;i++)
{
//因为a[0]是第一层,所以当前在i-1层,算的是跳到下一层后的能量,不能写成e=2*e-a[i+1]
e=2*e-a[i]; //计算得出,无论那种情况,都是这个式子(分类讨论也可以)
//注意2e要写成2*e!!!!!!
if(e<0)
return false;
//!!!极限情况下,当N(即n)取1e5,则e=2*e-a[i]是(2的1e5次方)*e,超过longlong的大小(8字节)
//此时e变成了负数,提前结束了,所以导致e的最小值会变大。
//设定 e>=1e5时就返回true,e就不会超出限制。
if(e>=1e5)
return true;///不知道这个为什么一定要加,说是可以加速判断
}
return true;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
//跳跃
int E; //energy 0---1e5,当E一开始就大于1e5,则一定一直加下去
int k=0;
int emin;
int l=1,r=1e5;//设定初始区间 ,这里是E的区间,注意E最大就是1e5
while(l<r) //l==r时,找到了最小值
{
emin=l+r>>1;
//对于能量,只要大于最低值,一定能够满足条件,只要emin不满足条件,emin一定在最低值的左边
//条件是能够完成所有跳跃
if(h(emin))
r=emin;
else
l=emin+1;
}
cout<<l;
return 0;
}