CF1954E Chain Reaction

有 $n$ 个怪物排成一排，第 $i$ 个怪物有 $a_i$ 点生命值。 每秒你可以选择一个存活的怪物，对其释放一次“连锁闪电”。闪电会对该怪物造成 $k$ 点伤害，并向左（即 $i$ 递减方向）和右（即 $i$ 递增方向）传播，对每个存活的怪物也造成 $k$ 点伤害。当闪电遇到已死亡的怪物或到达队列的开头/结尾时停止。怪物的生命值严格大于 $0$ 时视为存活。 例如，考虑如下情形：有三个怪物，生命值分别为 $[5, 2, 7]$，$k=3$。你可以在 $4$ 秒内消灭所有怪物： - 对第 $3$ 个怪物释放连锁闪电，生命值变为 $[2, -1, 4]$； - 对第 $1$ 个怪物释放连锁闪电，生命值变为 $[-1, -1, 4]$； - 对第 $3$ 个怪物释放连锁闪电，生命值变为 $[-1, -1, 1]$； - 对第 $3$ 个怪物释放连锁闪电，生命值变为 $[-1, -1, -2]$。 对于每个 $k$ 从 $1$ 到 $\max(a_1, a_2, \dots, a_n)$，计算消灭所有怪物所需的最少秒数。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示怪物的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$），表示每个怪物的生命值。

对于每个 $k$ 从 $1$ 到 $\max(a_1, a_2, \dots, a_n)$，输出消灭所有怪物所需的最少秒数。

由 ChatGPT 4.1 翻译