#10697. D - Strange Balls 奇怪的求 比赛编号240
D - Strange Balls 奇怪的求 比赛编号240
问题描述
Takahashi 有 N
个球。每个球上都有一个不小于 2 的整数 a_i
。他将这些球一个接一个地插入一个圆柱体中。
这些球由特殊材料制成。当有 k
个球(k ≥ 2
)上面写着相同的数字 k
时,这些球会消失。
对于每个 i
(1 ≤ i ≤ N
),求在插入第 i
个球后圆柱体中剩余的球的数量。
输入
输入的格式如下:
N
a_1
a_2
…
a_N
其中:
N
:球的数量。a_i
:第i
个球上写的数字。
输出
输出 N
行,第 i
行表示在插入第 i
个球后,圆柱体中剩余的球的数量。
限制
1 ≤ N ≤ 2 × 10^5
2 ≤ a_i ≤ 2 × 10^5
(1 ≤ i ≤ N
)- 输入中的所有值都是整数。
样例输入 1
5
3 2 3 2 2
样例输出 1
1
2
3
4
3
解释:
- 插入第1个球后,圆柱体中只有一个球,内容是:
3
。 - 插入第2个球后,圆柱体中有两个球,内容是:
3, 2
。 - 插入第3个球后,圆柱体中有三个球,内容是:
3, 2, 3
。 - 插入第4个球后,圆柱体中有四个球,内容是:
3, 2, 3, 2
。 - 插入第5个球后,圆柱体中有五个球,内容是:
3, 2, 3, 2, 2
。此时,两个连续的数字2
会消失,最终剩下的球是:3, 2, 3
,共3个。
解题思路
- 使用栈(Stack)来模拟圆柱体的插入与消失过程。
- 每次插入球时,检查栈顶是否存在相同的球,并检查它们的数量是否足够消失。
- 如果存在连续相同的球,数量达到该球的值
k
时,就将这些球从栈中移除。 - 每次插入之后,我们可以直接输出当前栈中球的数量。