AcWing 730，史上最全最精简的学习路线图

Geek_f90455

关注

发布于: 2 小时前

编号为 0 的建筑高度为 0 个单位，编号为 i 的建筑高度为 H(i)个单位。

起初，机器人在编号为 0 的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)-E 的能量值，否则它将得到 E-H(k+1)的能量值。

游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 N。

第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N)代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤105,

输入样例 1：

3 4 3 2 4

输出样例 1：

输入样例 2：

4 4 4

输出样例 2：

输入样例 3：

1 6 4

输出样例 3：

2.思路

思路:二分,答案所在区间为 1-1e5,具有单调性,且当 x>=E(min),从 E(min)往后的区间值都可以完成整个游戏,因此可以将整个区间一分为二，我们二分求边界 E(min)。

我们发现这样一个性质:当能量值大于游戏中建筑的最高值时,跳过最高建筑时能量值不变,在跳高度低于最高建筑时，能量值一直在增加,因此可以完成整个游戏。

当 H(k+1)>E，E=E-(H(k+1)-E)=2_E+H(k+1)

当 H(k+1)<=E,E=E+(E-H(k+1))=2_E+H(k+1) 综上在跳跃过程中，计算能量值公式为：E=2*E-H(k+1)

3…AC 代码


#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int h[N],maxn,n;
bool check(int E)  //我们带入一个初始能量值，检查它是否满足条件
{
    for(int i=1;i<=n;i++)
    {
        E=E*2-h[i];
        if(E<0)  return false;
        if(E>=maxn)  return true;
    }
    return true;
}
int main()

# 总结
面试前的“练手”还是很重要的，所以开始面试之前一定要准备好啊，不然也是耽搁面试官和自己的时间。
我自己是刷了不少面试题的，所以在面试过程中才能够做到心中有数，基本上会清楚面试过程中会问到哪些知识点，高频题又有哪些，所以刷题是面试前期准备过程中非常重要的一点。
**[下面我就把我整理的面试资料分享给有需要的读者朋友——戳这里免费获取](https://gitee.com/vip204888/java-p7)**
# 面试题及解析总结
![三年Java开发，刚从美团、京东、阿里面试归来，分享个人面经](https://static001.geekbang.org/infoq/78/78939cfc3047b37a562f0f5ea8b02394.png)
# 大厂面试场景
![三年Java开发，刚从美团、京东、阿里面试归来，分享个人面经](https://static001.geekbang.org/infoq/ee/eefc8e631d13bc8b88c38ea31ea36f2f.png)
# 知识点总结
![三年Java开发，刚从美团、京东、阿里面试归来，分享个人面经](https://static001.geekbang.org/infoq/19/19134d0757e5b0a4b7df8991bb5c22b0.png)

复制代码

发布于: 2 小时前阅读数: 2

Geek_f90455

关注

还未添加个人签名 2021.07.06 加入

还未添加个人简介

发布

暂无评论

创作场景

AcWing 730，史上最全最精简的学习路线图

2.思路

3…AC 代码

Geek_f90455

评论