P12166 [蓝桥杯 2025 省 C/Java A/研究生组] 冷热数据队列

题目描述

冷热数据队列 $q$ 可以看做由两个子队列组成：长度为 $n_1$ 的热数据队列 $q_1$ 和长度为 $n_2$ 的冷数据队列 $q_2$。当我们需要访问某个数据页 $p$ 时：

1. 若 $p$ 不在队列 $q$ 中（即既不在 $q_1$ 中，也不在 $q_2$ 中），则加载数据页 $p$，并插入到 $q_2$ 的首部。
2. 若 $p$ 已经在队列 $q$ 中，则将 $p$ 移动至 $q_1$ 首部。
3. 当 $q_1$ 或 $q_2$ 队列容量不足时，会将其尾部的数据页淘汰出去。
4. 当 $q_1$ 已满，但 $q_2$ 未满时，从 $q_1$ 中淘汰出的数据页会移动到 $q_2$ 首部。

输入格式

输入的第一行包含两个正整数 $n_1,n_2$，用一个空格分隔。

第二行包含一个整数 $m$，表示操作次数。

第三行包含 $m$ 个非负整数 $v_1,v_2,\cdots ,v_m$，表示依次访问到的数据页的编号，相邻整数之间使用一个空格分隔。

输出格式

输出两行。

第一行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 $q_1$ 中的数据页。

第二行包含若干个整数，相邻整数之间使用一个空格分隔，依次表示 $q_2$ 中的数据页。

输入输出样例 #1

输入 #1

3 3
10
1 2 3 4 3 2 2 1 3 4

输出 #1

4 3 2
1

说明/提示

样例说明

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$1\le n_1,n_2\le 10$，$1\le m\le 10$；
• 对于 $40\%$ 的评测用例，$1\le n_1,n_2\le 20$，$1\le m\le 100$；
• 对于 $60\%$ 的评测用例，$1\le n_1,n_2\le 100$，$1\le m\le 1000$；
• 对于 $80\%$ 的评测用例，$1\le n_1,n_2\le 10^3$，$1\le m\le 10^4$；
• 对于所有评测用例，$1\le n_1,n_2\le 10^4$，$1\le m\le 10^5$，$0\le v_i\le 10^4$。

C++实现

#include<bits/stdc++.h>
using namespace std;
int n1,n2,m,x,t;
pair<int,list<int>::iterator> d[1000005];//存储位置信息
list<int> q1,q2;//两个双向链表
map<int,bool> vis;//检查是否出现过
int main(){
	scanf("%d%d%d",&n1,&n2,&m);
	for(int i=1;i<=m;i++)    {
		scanf("%d",&x);
		if(vis[x]==false)        {
            vis[x]=true;
            q2.push_front(x);
            d[x].first=2;
            d[x].second=q2.begin();
        }
		else        {
			auto p=d[x];
			if(p.first==1) q1.erase(p.second);
			else q2.erase(p.second);
			q1.push_front(x);
            d[x].first=1;
            d[x].second=q1.begin();
		}
		if((int)q1.size()>n1)        {
			t=*q1.rbegin();
			q2.push_front(t);
			d[t].first=2;
            d[t].second=q2.begin();
			q1.pop_back();
		}
		if((int)q2.size()>n2)        {
			t=*q2.rbegin();
			vis[t]=0;
			q2.pop_back();
		}
    }
	for(auto i:q1) printf("%d ",i);
	printf("\n");
	for(auto i:q2) printf("%d ",i);
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容