算法1
思路:二分
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n;
int h[N];
bool check(int e){
for(int i=1;i<=n;i++){
e=e*2-h[i];//关键,当h(k+1)>e E-(H(k+1)-E)=2E-H(k+1)同理H(k+1)<E,E+E-H(k+1)=2E-H(k+1)
if(e>=1e5) return true;
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=1e5;//二分范围,写框架,然后根据题意写check函数
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
return 0;
}