Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届省赛真题-分布式队列
题目 3227:

蓝桥杯2024年第十五届省赛真题-分布式队列

时间限制: 3s 内存限制: 512MB 提交: 972 解决: 187

题目描述

小蓝最近学习了一种神奇的队列:分布式队列。简单来说,分布式队列包含 N 个节点(编号为 0 至 N − 1,其中 0 号为主节点),其中只有一个主节点,其余为副节点。主/副节点中都各自维护着一个队列,当往分布式队列中添加元素时都是由主节点完成的(每次都会添加元素到队列尾部);副节点只负责同步主节点中的队列。可以认为主/副节点中的队列是一个长度无限的一维数组,下标为 0, 1, 2, 3 . . . ,同时副节点中的元素的同步顺序和主节点中的元素添加顺序保持一致。

由于副本的同步速度各异,因此为了保障数据的一致性,元素添加到主节点后,需要同步到所有的副节点后,才具有可见性。

给出一个分布式队列的运行状态,所有的操作都按输入顺序执行。你需要回答在某个时刻,队列中有多少个元素具有可见性。

输入格式

第一行包含一个整数 N,表示节点个数。接下来包含多行输入,每一行包含一个操作,操作类型共有以下三种:add、sync 和 query,各自的输入格式如下:

1. add element:表示这是一个添加操作,将元素 element 添加到队列中;

2. sync follower_id:表示这是一个同步操作,follower_id 号副节点会从主节点中同步下一个自己缺失的元素;

3. query:查询操作,询问当前分布式队列中有多少个元素具有可见性。

输出格式

对于每一个 query 操作,输出一行,包含一个整数表示答案。

样例输入

3
add 1
add 2
query
add 1
sync 1
sync 1
sync 2
query
sync 1
query
sync 2
sync 2
sync 1
query

样例输出

0
1
1
3

提示

【样例说明】

执行到第一个 query 时,队列内容如下:

0:[1,2]
1:[]
2:[]
两个副节点中都无元素,因此答案为 0。
执行到第二个 query 时,队列内容如下:
0:[1,2,1]

1:[1,2]

2:[1]

只有下标为 0 的元素被所有节点同步,因此答案为 1。执行到第三个 query 时,队列内容如下:0:[1,2,1]1:[1,2,1]2:[1]

只有下标为 0 的元素被所有节点同步,因此答案为 1。执行到第四个 query 时,队列内容如下:0:[1,2,1]1:[1,2,1]2:[1,2,1]

三个元素都被所有节点同步,因此答案为 3。

【评测用例规模与约定】

对于 30% 的评测用例:1 ≤ 输入的操作数 ≤ 100。

对于 100% 的评测用例:1 ≤ 输入的操作数 ≤ 2000,1 ≤ N ≤ 10,1 ≤f ollower_id < N,0 ≤ element ≤ 105

标签