自动搬运

查看原文

来自洛谷，原作者为

	YBa2Cu3O7 q2231734756欢迎交流|准备转码|对计算科学感兴趣|以撒群星杀戮尖塔文明6玩家|psp露蒂丝单推mmr

搬运于2025-08-24 23:13:20，当前版本为作者最后更新于2025-04-13 21:51:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

背景简介

最近最少使用（LRU）算法是一种常用的缓存淘汰算法，用于在缓存空间不足时决定哪些数据应该被移除。其基本思想是，如果一个数据最近被访问过，那么它将来被访问的概率也会更高。因此，当缓存空间不足时，应该优先淘汰最久未被访问的数据。

基于LRU原理的各种变体经常被应用到操作系统的内存页面置换策略和数据库的缓冲池管理中。

算法描述

LRU算法

使用双向链表+哈希表的组合结构实现时间复杂度 $O(1)$ 的插入，查找和删除。其中双向链表描述了历史访问顺序，哈希表记录了页面编号到链表节点指针的映射，用于查找和确定位置。

对于要调用的新页面，先检查是否已经存在于队列中，这是通过查哈希表来实现的。如果已经存在，那么先将这个节点移出队列，再放到队首，否则执行插入流程。

将新页面插入到队首，插入前检查队列容量是否已满，如果满了则先把队尾页面出队（这里描述的名称似乎和普通队列刚好反过来），再将新页面入队，同时用哈希表记录页面编号到链表节点指针的映射。

出队时除了整理链表中的指针关系，还要记得在哈希表中删除对应的映射。

冷热数据队列

本题相当于在四条额外规则下维护两个LRU队列。在这种情况下，多出了热队列中的页面出队后还要向冷队列中入队，第一次调用要先向冷队列中入队等操作。

代码解释

这种大模拟题最好还是写得工程化一些，语义明确，减少耦合，能少写很多不必要的代码，也便于debug。

代码中的结构体 node 作为双向链表的节点，存储页面编号和前后节点的两个指针。类 lru 即为LRU算法的实现，为了方便插入和删除，在双向链表的头尾各添加一个辅助节点，其中不存储任何信息。类 hotcoldq 是解决问题的核心类，包括两个LRU队列作为成员变量和插入函数作为成员函数。其中 q1 表示热队列，q2 表示冷队列。

成员函数 lru::move 是用来配合做移动操作的，减少 new 的次数。其它诸如 lru::begin 的函数则是一点个人代码爱好（伪装成标准库），本质上是可以不用的。正常来说 lru 应该有一个自己的插入函数，但是本题没有用到就没有特别去写了，它本质上就是一个 new/move+push 的组合。

这里除输出外没有需要遍历的操作，因此没有添加相应的迭代器类，直接操纵了指针。重载的函数也仅仅是为了方便使用，其中的指导思想是，任何与应用逻辑无关的部分，都应该在类成员函数中处理而不是在外部调用时。

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct node {
	T num;
	node* nxt;
	node* pre;
	node(T n = 0) :num(n), nxt(0), pre(0) {}
};

template <typename T>
class lru {
	size_t maxsz;
	size_t sz;
	node<T>* q;
	node<T>* qend;
	unordered_map<T, node<T>*> ump;

public:
	lru(size_t n) :sz(0), maxsz(n) {
		q = new node<T>;
		qend = new node<T>;
		q->nxt = qend;
		qend->pre = q;
	}

	size_t size() {
		return sz;
	}

	size_t maxsize() {
		return maxsz;
	}

	bool full() {
		return sz == maxsz;
	}

	node<T>* end() {
		return qend;
	}

	node<T>* begin() {
		return q->nxt;
	}

	void push(node<T>* p) {
		if (full()) {
            erase(end()->pre);
        }
		auto nxt = q->nxt;
		p->nxt = nxt;
		nxt->pre = p;
		p->pre = q;
		q->nxt = p;
		++sz;
		ump[p->num] = p;
	}

	void push(T n) {
		auto* p = new node<T>(n);
		push(p);
	}

	node<T>* move(node<T>* p) {
		auto pre = p->pre;
		auto nxt = p->nxt;
		pre->nxt = nxt;
		nxt->pre = pre;
		--sz;
		ump.erase(p->num);
		return p;
	}

	node<T>* move(T n) {
		return move(ump[n]);
	}

	void erase(node<T>* p) {
		move(p);
		delete p;
	}

	void erase(T n) {
		erase(ump[n]);
	}

	node<T>* find(T n) {
		if (ump.find(n) == ump.end()) {
			return end();
		}
		else {
			return ump[n];
		}
	}

	void output() {
		for (node<T>* p = begin(); p != end(); p = p->nxt) {
			cout << p->num << ' ';
		}
	}

	~lru() {
		auto p = begin();
		while (p != qend) {
			auto q = p;
			p = p->nxt;
			delete q;
		}
		delete q;
		delete qend;
	}

};

template <typename T>
class hotcoldq {
	lru<T> q1, q2;

public:
	hotcoldq(T n, T m) :q1(n), q2(m) {}

	void insert(T n) {
		bool ck1 = (q1.find(n) == q1.end());
		bool ck2 = (q2.find(n) == q2.end());
		if (ck1 && ck2) {
			if (q2.full()) {
				q2.erase(q2.end()->pre);
			}
			q2.push(n);
		}
		else {
			node<T>* p = 0;
			if (!ck1) {
				p = q1.move(n);
			}
			else if (!ck2) {
				p = q2.move(n);
				if (q1.full()) {
					auto q = q1.move(q1.end()->pre);
					q2.push(q);
				}
			}
			q1.push(p);
		}
	}

	void output() {
		q1.output();
		cout << '\n';
		q2.output();
	}

	~hotcoldq() = default;

};

int main() {
	int n, m;
	cin >> n >> m;
	hotcoldq<int> q(n, m);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int v;
		cin >> v;
		q.insert(v);
	}
	q.output();
	return 0;
}