字节跳动笔试真题，一道巧妙的二分题，你能搞定吗？

点击上方蓝字，关注并星标，和我一起学技术。

大家好，我们今天继续解析字节跳动的笔试真题。

今天我选择的是这套题的最后一题，从难度上来看说这道题难度同样不是很大，但是有一些巧妙，需要有一定的经验以及问题分析能力。算法题有意思的地方也就在这里，很多时候干想是不行的，需要我们深入分析，寻找一些基点。

题目链接：https://www.nowcoder.com/question/next?pid=16516564&qid=362294&tid=40247384

好了，废话不多说了，我们来看题吧。

题意

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。

起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。

游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

输入描述:

第一行输入，表示一共有 N 组数据.

第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度

输出描述:

输出一个单独的数表示完成游戏所需的最少单位的初始能量

输入例子1:

5
3 4 3 2 4

输出例子1:

4

输入例子2:

3
4 4 4

输出例子2:

4

输入例子3:

3
1 6 4

输出例子3:

3

题解

题意当中漏了一个条件，就是N和H[i]的范围，由于这道题其实不是字节跳动的原创题，所以我从其他地方找到了这个的相关信息，

。

如果大家对范围比较敏感的话，看到

这个量级应该会有很多想法，比如这道题的解法很有可能是

。有了范围之后，从而可以进一步对可以选择的算法有进一步的猜测和思考。这里我们假设大家没有这样的敏感性，想不到从这点入手，那么如果是正面进攻，这道题应该怎么解决呢？

这是一个跳棋游戏，我们从最左侧跳到最右侧，我们关注一下每一次跳跃的条件。首先，每一次跳跃只能移动一格，在移动的过程当中我们的能量会发生变化。我们假设当前的能量是E，我们每次的变化量是E - H[k+1]。当E大于H[k+1]的时候这个变化量是正值，否则是负值。也就是说我们每次从k移动到k+1，能量E都会变成E + E - H[k+1] = 2E - H[k+1]。

这个递推公式有了之后，我们要做的就是找到一个起始的最小E，使得在整个过程当中能量不会成负值。这里就很难办了，由于每一次跳跃能量的变化量都和能量本身相关，我们没办法推导出起始能量以及变量量的关系。换句话说我们想要知道某一个起始能量在中途会不会变成负值，我们只能通过遍历来实现。

这个结论固然是一个难点，但其实也是一个提示，相当于帮我们排除掉了一些错误选项。我们在做题的时候要注意这些点，有的时候很有可能就是某一个难点帮助我们找到了方向。

当我们深入分析题意的时候，又可以找到另外一个关键点。这个关键点当E足够大时，一定可以保证中途不会变成负值。所谓的足够大其实是很清晰的，比如我们很容易可以发现当

时。因为每一次移动时，E会变成

。E大于所有H中的最大值就可以保证每一次移动都必然是增加的。其次我们又可以发现

这个函数是一个递增函数，也就是说E越大，最终的结果越大。

不知道大家到这里有没有什么想法，其实到这里已经很清楚了。因为每一步的结果都是递增的，所以我们可以使用二分来找到这个刚好可以构成所以位置均为非负的E值。并且我们二分的区间都已经确定了，是

，这是一个左开右闭区间，剩下的就是在这个区间里做二分。

到这里还没有结束，还有一个小trick，我们注意到了

这个式子让我们想到了是递增函数可以二分。它其实还有一个隐藏的关键信息，就是它的增长率可以非常大，如果E足够大，而

，那么每次移动都会使得E翻倍。显然这是非常危险的，很容易超界，所以我们要进行判断，当某一个位置的E超过max的时候就不用往后判断了，因为一定不会再陷入负数。

大家可以参考代码，寻找更多的细节。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
#define pii pair<int, int>
using namespace std;
const int N=1000050;
const long long Mod=99997867;


int main() {
    vector<int> buildings;
    int n;
    // 找到所有H中的最大值
    int maxi = 0;
    scanf("%d", &n);
    rep(i, 0, n) {
        int x;
        scanf("%d", &x);
        maxi = max(maxi, x);
        buildings.push_back(x);
    }

    int l = -1, r = maxi;
    int cur;

    while (r - l > 1) {
        int m = mid;
        cur = m;
        bool flag = false;
        rep(i, 0, buildings.size()) {
            cur += (cur - buildings[i]);
            if (cur < 0) {
                flag = true;
                break;
            }
            // 当前能量已经大于maxi时不用判断了，一定不会陷入负数
            if (cur > maxi) {
                break;
            }
        }

        // 左开右闭区间的二分方法
        if (flag || cur < 0) {
            l = m;
        }else {
            r = m;
        }
    }
    printf("%d\n", r);
    return 0;
}

这道题基本上想到二分就没问题了，只是很多人估计不敢往二分上想。不过我想到了二分还是在trick上卡了一会，可见这题还是没有那么简单。总的来说这题质量还是很不错的，非常适合大家练习。

今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、在看、转发）