怎样使用二分来做;
看题目是否具有二段性 或者单调性;
单调性属于二段性;
怎样看单调性:
初始时E0
数学归纳法推出:Ei撇 都是大于Ei的
达到某一个值就一定能够成功,等于maxh;return true; 防止中间过程爆int
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010;
int n;
int h[N];
// 查找最小值的能量e
bool check(int e){
for(int i=0;i<n;i++){
e=2*e-h[i];
if(e<0){ //判断中间有没有小于0的能量
return false;
}else if(e>100000){ // 达到某一个值就一定能够成功,防止爆int
return true;
}
}
return true;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>h[i];
}
int l=0,r=100000;
while(l<r){
int mid=(l+r)/2;
if(check(mid)){ //判断当前位置上的能量e是否满足条件
r=mid; // 要求找最小的能量E
}else{
l=mid+1;
}
}
cout<<r<<endl;
return 0;
}
标签:return,int,机器人,730,include,true,单调,AcWing
From: https://www.cnblogs.com/mengfengguang/p/16853359.html