CF1866G Grouped Carriages

Pak Chanek 发现，在早晨和下午的发车高峰时段，列车车厢总是非常拥挤。因此，需要在各个车厢之间实现平衡，避免只有少数几个车厢过于拥挤。 一列火车有 $N$ 节车厢，从左到右编号为 $1$ 到 $N$。第 $i$ 节车厢初始有 $A_i$ 名乘客。所有车厢之间通过车厢门相连，即对于每个 $i$（$1\leq i\leq N-1$），第 $i$ 节车厢和第 $i+1$ 节车厢通过一扇双向门相连。 每位乘客都可以在车厢之间移动，但列车规定，对于每个 $i$，从第 $i$ 节车厢出发的乘客最多只能通过 $D_i$ 扇门。 定义 $Z$ 为移动后同一车厢中最多的乘客数。Pak Chanek 想知道，$Z$ 的最小可能值是多少。

第一行包含一个整数 $N$（$1 \leq N \leq 2\cdot10^5$），表示车厢数。 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$0 \leq A_i \leq 10^9$），表示每节车厢初始的乘客数。 第三行包含 $N$ 个整数 $D_1, D_2, \ldots, D_N$（$0 \leq D_i \leq N-1$），表示每节车厢出发的乘客最多能通过的门数。

输出一个整数，表示 $Z$ 的最小可能值。

一种最优策略如下： - 第 $1$ 节车厢的 $5$ 人移动到第 $4$ 节车厢（经过 $3$ 扇门）。 - 第 $5$ 节车厢的 $3$ 人移动到第 $3$ 节车厢（经过 $2$ 扇门）。 - 第 $6$ 节车厢的 $2$ 人移动到第 $5$ 节车厢（经过 $1$ 扇门）。 - 第 $6$ 节车厢的 $1$ 人移动到第 $7$ 节车厢（经过 $1$ 扇门）。 此时每节车厢的乘客数变为 $[2,4,5,5,4,5,4]$。 由 ChatGPT 4.1 翻译