思路
对于含有 单调性的题目,一般都可以使用二分来解决,但是如果没有单调性,也不是说就一定无法使用 二分解决,简单说就是含有 二段性 的条件,都可以使用二分思想解决,就是可以用一个性质来区分出所有的量,一边是满足该性质的,一边是不满足该性质的
对于本题,我们可以验证其单调性,对于初始的 E0
如果成立的,那么对于 E^>=E0
是否都一定可以满足条件呢?由题可以得到 $E=2E-h_{k+1}$ , 所以对于 E^
都是成立的,既然有单调性,就可以考虑使用二分思想来实现了
下面的代码中有些细节还是要注意的,比如咋 判断越界的时候,如果超出范围了,那么对于后面的一定就是可以的,所以直接返回 true了
代码
#include <iostream>
using namespace std;
const int N=100010;
int h[N];
int n;
//整数二分的思想,找到满足条件的一部分和不满足条件的一部分
bool check(int e)
{
for(int i=0;i<n;i++)
{
e=2*e-h[i];
//如果已经超过最大值了,则后面的一定满足
if(e>=1e5)
{
return true;
}
//中间如果小于0,就说明不满足条件了
if(e<0)
{
return false;
}
}
return true;
}
int main()
{
cin.tie();
cin>>n;
for(int i=0;i<n;i++)
{
cin>>h[i];
}
//整数二分的模板
int l=0,r=1e5;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
cout<<l<<"\n";
return 0;
}