#10696. D - Cylinder 圆柱体 比赛编号247
D - Cylinder 圆柱体 比赛编号247
问题描述
我们有一个水平的圆柱体。给定 Q
个查询,按照给定的顺序处理它们。每个查询是以下两种类型之一:
1 x c
:向圆柱体的右端插入c
个球,每个球上写有数字x
。2 c
:取出圆柱体中最左边的c
个球,并打印出这些球上数字的和。
我们假设球在圆柱体中的顺序永远不会改变。
输入
输入格式如下:
Q
query1
query2
...
queryQ
每个查询 queryi
是以下两种格式之一:
1 x c
:表示插入c
个数字为x
的球。2 c
:表示取出c
个最左边的球,并计算它们的和。
输出
对于每个 2 c
类型的查询,输出这些球的数字之和,并在每个输出结果之间换行。
限制
1 ≤ Q ≤ 2 × 10^5
0 ≤ x ≤ 10^9
1 ≤ c ≤ 10^9
- 每当有类型为
2 c
的查询时,圆柱体中至少有c
个球。 - 输入的所有值都是整数。
样例输入 1
4
1 2 3
2 2
1 3 4
2 3
样例输出 1
4
8
解释:
- 第1个查询:插入3个数字为2的球,圆柱体现在有(2, 2, 2)这三个球。
- 第2个查询:取出圆柱体中最左边的2个球,取出的球是(2, 2),它们的和为4,输出4。
- 第3个查询:插入4个数字为3的球,圆柱体现在有(2, 3, 3, 3, 3)这五个球。
- 第4个查询:取出圆柱体中最左边的3个球,取出的球是(2, 3, 3),它们的和为8,输出8。
样例输入 2
2
1 1000000000 1000000000
2 1000000000
样例输出 2
1000000000000000000
解释:
- 第1个查询:插入1000000000个数字为1000000000的球,圆柱体现在有1000000000个数字为1000000000的球。
- 第2个查询:取出1000000000个最左边的球,取出的球是(1000000000,1000000000,...),它们的和是
1000000000 * 1000000000
,输出1000000000000000000
。
样例输入 3
5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
样例输出 3
(没有输出)
解释:
- 所有的查询都是插入球的操作,且没有任何
2 c
类型的查询,因此没有输出。
解题思路
这个问题可以使用队列(Queue)来模拟。对于每个查询:
- **类型
1 x c
**:将c
个数字为x
的球插入到队列的末尾。 - **类型
2 c
**:从队列的前面取出c
个球,并计算它们的和。
因为输入的 Q
查询数量最大为 2 * 10^5
,所以我们需要确保每个操作的时间复杂度尽可能低。队列(deque
)适合用来执行这种插入和删除操作,因为其时间复杂度是常数级别的。