Python 版递推题解
题目描述
给定一组数列 $N$,每次 $E_i$ 的取值由上一个 $E_{i-1}$ 和 $N_i$ 决定,希望 $E_i$ 一直非负。
算法1
递推
由题目描述,我们可以得出第 $k$ 个能量:
$E_k = E_{k-1}-(N_k-E_{k-1}) \quad \text{if } N_k>E_{k-1}$
$E_k = E_{k-1}+(E_{k-1}-N_k) \quad \text{if } N_k<E_{k-1}$
$E_k = 2E_{k-1} - N_k$
因此我们可以递推得到初始值 $E_0$
$E_k = 2E_{k-1} - N_k = 4E_{k-2} - 2N_{k-1} - N_k = 8E_{k-3} - 4N_{k-2} - 2N_{k-1} - N_k = \dots $
$E_k = 2^kE_0 - \sum_{i=1}^{k} 2^{k-i}N_i > 0$
$$
E_0 = \left \lceil \frac{\sum_{i=1}^{k} 2^{k-i}N_i}{2^k} \right \rceil
$$
时间复杂度
$O(n)$
Python 代码
N = int(input())
N_temp = N
Hk = list(map(int, input().split(" ")))
Hk_wsum = 0
i = 0
while N_temp:
N_temp -= 1
Hk_wsum += 2**N_temp * Hk[i]
i += 1
E0 = Hk_wsum // (2**N) + (Hk_wsum % (2**N) != 0) # 若不能整除则加一,相当于向上取整
print(E0)