AcWing 730. 机器人跳跃问题
原题链接
中等
作者:
虚实相依
,
2024-04-12 20:32:27
,
所有人可见
,
阅读 1
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1e5+10;
typedef long long ll;
int n;
int w[N];
int mx;
bool check(ll mid)
{
ll x=mid;
for(int i=1;i<=n;i++)
{
x+=(x-w[i]);
if(i<=n && x<0) return false;
else if(x>=mx) return true;
// cout<<x<<endl;
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
mx=max(mx,w[i]);
}
ll l=1,r=1e5;
while(l<r)
{
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}