蓝桥杯历届真题 #分布式队列 (Java,C++)

文章目录

题目解读
[蓝桥杯 2024 省 Java B] 分布式队列
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- - 样例输入 #1
  - 样例输出 #1
- 提示
思路
完整代码

题目解读

题目链接

[蓝桥杯 2024 省 Java B] 分布式队列

题目描述

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

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

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

输入格式

第一行包含一个整数 $N$ ，表示节点个数。

接下来包含多行输入，每一行包含一个操作，操作类型共有以下三个：add、sync 和 query，各自的输入格式如下：

add element：表示这是一个添加操作，将元素 $e l e m e n t$ 添加到队列中；
sync follower_id：表示这是一个同步操作， $follower\_id$ 号副节点会从主节点中同步下一个自己缺失的元素；
query：查询操作，询问当前分布式队列中有多少个元素具有可见性。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

提示

【样例说明】

执行到第一个 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$ 。

【评测用例规模与约定】

设输入的操作数为 $q$ 。

对于 $30\%$ 的评测用例： $1\leq q \leq 100$ 。

对于 $100\%$ 的评测用例： $1\leq q\leq 2000$ ， $1\leq N\leq 10$ ， $1\leq follower\_id<N$ ， $0\leq element\leq10^5$ 。

数据保证执行同步操作时， $follower\_id$ 号副节点一定缺失元素。

思路

由于最多有10个结点,可以采用暴力的方法
使用数组进行模拟
数组的下标代表第几个队列
数组的大小代表当前队列有几个元素
由于同步元素是同步主队列的下一个元素,因此我们不需要关心具体的元素值,只需要关心有几个元素即可
如果是add操作,我们只需要让其指定的队列元素+1即可,注意:要注意同步的个数不能超过主队列元素个数
查询的时候遍历每个队列,其最小的值就是可见的元素数量

完整代码

#include<bits/stdc++.h>using namespace std;const int N = 15;int cnt[N];int n;int check(){int res=2000;for(int i=1; i<n; i++){res=min(cnt[i],res);}return res;
}int main(){cin>>n;string op;int num;while(cin>>op){//主队列用0号结点if(op=="add"){cin>>num;cnt[0]++;}else if(op=="sync"){cin>>num;if(cnt[num]<cnt[0])cnt[num]++;}else{cout<<check()<<endl;}}return 0;
}

java">import java.util.Scanner;class Main{static int N =15;static int cnt[] = new int[N];static Scanner sc = new Scanner(System.in);static int n =sc.nextInt();public static void main(String[] args) {String op;int num;while(sc.hasNext()){op=sc.next();if(op.equals("add")){num=sc.nextInt();cnt[0]++;}else if(op.equals("sync")){num=sc.nextInt();if(cnt[num]<cnt[0])cnt[num]++;}else{System.out.println(check());}}}static int check(){int res=2000;for(int i=1; i<n; i++){res=Math.min(cnt[i],res);}return res;}
}