问题转化

本题可以转化为一个流量调度问题：我们需要将各楼层的初始人数 $a_i$ 调整为目标人数 $b_i$，通过相邻楼层之间的楼梯移动人员。每个楼梯单位时间只能单向通过一人。

设 $c_i = a_i - b_i$，表示第 $i$ 层需要净流出的人数（若 $c_i > 0$ 则需要向上或向下输出人员，若 $c_i < 0$ 则需要输入人员）。

关键观察

1. 前缀和性质：定义 $S_k = \sum_{i=1}^k c_i$，表示前 $k$ 层净需求人数。由于总人数守恒，$S_n = 0$。

2. 时间下界：最少需要的时间等于所有前缀和绝对值的最大值：

   $$T = \max_{1 \le k \le n} |S_k|$$

   这个结论的直观理解是：$|S_k|$ 表示前 $k$ 层与后 $n-k$ 层之间需要交换的人数，这些交换必须通过第 $k$ 层与第 $k+1$ 层之间的楼梯完成。

算法思路

1. 计算差值数组 $c_i = a_i - b_i$
2. 计算前缀和 $S_k = \sum_{i=1}^k c_i$
3. 答案即为 $\max |S_k|$

时间复杂度：$O(n)$，满足 $n \le 10^6$ 的要求。

正确性证明

考虑任意相邻两层 $i$ 和 $i+1$ 之间的楼梯：

• 如果 $S_i > 0$，表示前 $i$ 层人数过剩，需要向第 $i+1$ 层及以后输送 $S_i$ 人
• 如果 $S_i < 0$，表示前 $i$ 层人数不足，需要从第 $i+1$ 层及以前接收 $|S_i|$ 人

由于每个楼梯单位时间只能单向通过一人，所以至少需要 $|S_i|$ 个单位时间来完成这些人员的流动。对所有 $i$ 取最大值即得到总时间下界。

样例验证

对于样例：

n = 3
a = [1, 0, 1]  
b = [0, 2, 0]
c = [1, -2, 1]
S = [1, -1, 0]
max|S| = 1

答案为 1，符合样例输出。