题目描述

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)\backslash ;=\backslash ;2\backslash times\; E(n\backslash ;-1)\backslash ;-\backslash ;H(n)$ ，得 $E(n)=2^n\times E(0)-{\sum }_{i=1}^{n}H(i)\times 2^{n-i}E(n)\backslash ;=\backslash ;2^n\backslash times\; E(0)\backslash ;-\backslash ;\backslash sum\_\{i\backslash ;=\backslash ;1\}^nH(i)\backslash ;\backslash times\backslash ;2^\{n-i\}$ ；
而 $E(n)\ge 0E(n)\backslash ;\backslash geq\backslash ;0$ ，得 $2^n\times E(0)\ge {\sum }_{i=1}^{n}H(i)\times 2^{n-i}2^n\backslash times\; E(0)\backslash ;\backslash geq\backslash ;\backslash sum\_\{i\backslash ;=\backslash ;1\}^nH(i)\backslash ;\backslash times\backslash ;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)\backslash ;=\backslash ;2\backslash times\; E(n\backslash ;-1)\backslash ;-\backslash ;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;
} 

时间复杂度：O(n)

欢迎讨论交流！ 博客原文跳转链接