[//]: # 机械人跳跃

题目描述

有N座高度为H(i),的建筑，机器人从零点开始跳跃，e为能量每次消耗2*e-H(i)的能量。
问至少以多少能量值开始游戏，才可以保证完成。
1≤N,H(i)≤10^5 ,

样例

输入：
5
3 4 3 2 4
输出：
4

二分法

这是一道相对简单的二分题，只要想到使用二分便非常简单。（注意边界问题）
1.由题意知不管下一个建筑物的高度是否高于现有能量能量的变化总为2*e-H[i];
2.最优值问题，能量有明确的范围，故使用二分，将最优解问题转化为判断问题；

O(n logn)

参考文献

yxc视频
yxc代码
个人二分笔记

C++ 代码

代码非常简单可作为二分模板题

#include <iostream>
using namespace std;
const int N=1e5+10;
int h[N],n;

bool check(int mid)//判定能量是否够用 
{
    for(int i=1;i<=n;i++)
    {
        mid =2 * mid - h[i];
        if(mid<0) return false;
        else if(mid >= 1e5) return true;
    }
    return true;
}

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)cin>> h[i];

    int i= 0,j= 1e5;//二分边界 
    while(i<j)
    {
        int mid = i + j >> 1;
        if(check(mid))j = mid;
        else i = mid + 1;
    }
    cout<<j;
    return 0;
}

相关例题

个人认为难度由小变大
AcWing：
789.数的范围
790.数的三次方根
680.切绳子
1227.分巧克力
1236.递增三元组