题目描述

https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71

题解

二分法

curE 在模拟跳跃时如果值大于 maxE 就可以结束了，一定能完成游戏，继续加下去反而会导致溢出。
注意 curE 一定要与 maxE 比较，而不能与 right 比较，比如题目示例三会答案错误。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n, 0);
    int maxE = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        maxE = max(maxE, h[i]);
    }

    int left = 0, right = maxE;
    while (left <= right) {
        int mid = (left + right) / 2;
        long long curE = mid;
        for (int i = 0; i < n; i++) {
            curE += curE - h[i];
            // 提前结束避免 long long 溢出
            if (curE > maxE || curE < 0)
                break;
        }
        if (curE > 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << left << endl;
    return 0;
}

时间复杂度：O(nlogn)

公式推导

由 $E(n)\;=\;2\times E(n\;-1)\;-\;H(n)$ ，得 $E(n)\;=\;2^n\times E(0)\;-\;\sum_{i\;=\;1}^nH(i)\;\times\;2^{n-i}$ ；
而 $E(n)\;\geq\;0$ ，得 $2^n\times E(0)\;\geq\;\sum_{i\;=\;1}^nH(i)\;\times\;2^{n-i}$ 。
即为不等式求临界值的问题，解得 E(0) 的最小值，向上取整。
解法参考

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, h;
    // long long 只能过 3 个样例，float 能过 7 个，double 全过
    double E = 0.0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h;
        E += h * pow(2, n - i);
    }
    cout << ceil(E / pow(2, n)) << endl;
    return 0;
}

时间复杂度：O(nlogn)，因为 pow(x, y) 的时间复杂度为 log(y)
Pow(x,n)的O(logN)时间复杂度实现

当然，如果提前计算 2 的 0 ~ n 次方结果并存储在数组中，那时间复杂度：O(n)
至于空间复杂度的额外开销，值得一提的是，该解法并没有存储建筑的高度。

逆推

同理公式推导，由 $E(n)\;=\;2\times E(n\;-1)\;-\;H(n)$ ，那假定 E(n) = 0，开始逆推。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int need_energy = 0;
    for (int i = n - 1; i >= 0; i--) {
        // 这里 + 1 是向上取整
        need_energy = (need_energy + h[i] + 1) / 2;
    }
    cout << need_energy << endl;
    return 0;
}