如何实现整数二分

本篇内容主要讲解“如何实现整数二分”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“如何实现整数二分”吧!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

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];
        //可以证明e>=hmax时，一定符合
        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]);
    //区间 (可以证明，只要E>=hmax，Ek+1一定成立)
    int l=0,r=1e5;
    //性质（左端点 缩右 +1）
    while(l<r){
        int m=(l+r)>>1;
        if(check(m)) r=m;
        else l=m+1;
    }
    cout<<l;
    return 0;
}

到此，相信大家对“如何实现整数二分”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！