311239: CF1954E. Chain Reaction
Description
There are $n$ monsters standing in a row. The $i$-th monster has $a_i$ health points.
Every second, you can choose one alive monster and launch a chain lightning at it. The lightning deals $k$ damage to it, and also spreads to the left (towards decreasing $i$) and to the right (towards increasing $i$) to alive monsters, dealing $k$ damage to each. When the lightning reaches a dead monster or the beginning/end of the row, it stops. A monster is considered alive if its health points are strictly greater than $0$.
For example, consider the following scenario: there are three monsters with health equal to $[5, 2, 7]$, and $k = 3$. You can kill them all in $4$ seconds:
- launch a chain lightning at the $3$-rd monster, then their health values are $[2, -1, 4]$;
- launch a chain lightning at the $1$-st monster, then their health values are $[-1, -1, 4]$;
- launch a chain lightning at the $3$-rd monster, then their health values are $[-1, -1, 1]$;
- launch a chain lightning at the $3$-th monster, then their health values are $[-1, -1, -2]$.
For each $k$ from $1$ to $\max(a_1, a_2, \dots, a_n)$, calculate the minimum number of seconds it takes to kill all the monsters.
InputThe first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of monsters.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the health points of the $i$-th monster.
OutputFor each $k$ from $1$ to $\max(a_1, a_2, \dots, a_n)$, output the minimum number of seconds it takes to kill all the monsters.
ExamplesInput3 5 2 7Output
10 6 4 3 2 2 1Input
4 7 7 7 7Output
7 4 3 2 2 2 1Input
10 1 9 7 6 2 4 7 8 1 3Output
17 9 5 4 3 3 3 2 1
Output
E. 链式反应
有 $ n $ 个怪物站在一行中,第 $ i $ 个怪物有 $ a_i $ 点生命值。
每秒钟,你可以选择一个**活着的**怪物对其发动链状闪电。闪电对其造成 $ k $ 点伤害,并传播到左边(向减少的 $ i $ 方向)和右边(向增加的 $ i $ 方向)的**活着的**怪物,对每个怪物造成 $ k $ 点伤害。当闪电到达一个死怪物或行首/行尾时,它停止。如果一个怪物的生命值严格大于 $ 0 $,则认为它是活着的。
对于每个 $ 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 $)——第 $ i $ 个怪物的生命值。
输出:
- 对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $,输出杀死所有怪物所需的最少秒数。
示例输入输出:
输入:
```
3
5 2 7
```
输出:
```
10 6 4 3 2 2 1
```
输入:
```
4
7 7 7 7
```
输出:
```
7 4 3 2 2 2 1
```
输入:
```
10
1 9 7 6 2 4 7 8 1 3
```
输出:
```
17 9 5 4 3 3 3 2 1
```题目大意: E. 链式反应 有 $ n $ 个怪物站在一行中,第 $ i $ 个怪物有 $ a_i $ 点生命值。 每秒钟,你可以选择一个**活着的**怪物对其发动链状闪电。闪电对其造成 $ k $ 点伤害,并传播到左边(向减少的 $ i $ 方向)和右边(向增加的 $ i $ 方向)的**活着的**怪物,对每个怪物造成 $ k $ 点伤害。当闪电到达一个死怪物或行首/行尾时,它停止。如果一个怪物的生命值严格大于 $ 0 $,则认为它是活着的。 对于每个 $ 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 $)——第 $ i $ 个怪物的生命值。 输出: - 对于每个 $ k $ 从 $ 1 $ 到 $ \max(a_1, a_2, \dots, a_n) $,输出杀死所有怪物所需的最少秒数。 示例输入输出: 输入: ``` 3 5 2 7 ``` 输出: ``` 10 6 4 3 2 2 1 ``` 输入: ``` 4 7 7 7 7 ``` 输出: ``` 7 4 3 2 2 2 1 ``` 输入: ``` 10 1 9 7 6 2 4 7 8 1 3 ``` 输出: ``` 17 9 5 4 3 3 3 2 1 ```