B-5 LRU-K 缓存
分数 25
LRU 全称为 LeastRecently Used，即“最近最少使用”。LRU 缓存机制是指，当缓存满了，而缓存区外面的一个新数据被调用的时候，将缓存中最近最少使用（即最长时间没有被使用过）的数据清除，为新数据开辟出空间。
LRU-K 是 LRU 算法的变种，K 代表最近使用的次数，LRU 可以认为是 LRU-1。不同于 LRU 算法的是，LRU-K算法需要维护两套队列（历史访问队列，缓存队列）。当历史访问队列中的数据被命中 K 次后，数据才会移动至缓存队列中。
例如：假设所有队列长度为 5，初始内存中没有数据。使用 LRU-2 算法，数据访问顺序为：9，5，6，7，8，3，8，9，5，9，8，3，4，7，5，6。则历史访问队列和缓存队列的变化如下表所示：
访问元素 历史访问队列 缓存队列
9,5,6,7,8 9,5,6,7,8 空
3 5,6,7,8,3 空
8 5,6,7,3 8
9 5,6,7,3,9 8
5 6,7,3,9 8,5
9 6,7,3 8,5,9
8 6,7,3 5,9,8
3 6,7 5,9,8,3
4 6,7,4 5,9,8,3
7 6,4 5,9,8,3,7
5 6,4 9,8,3,7,5
6 4 8,3,7,5,6
你的任务就是实现这种 LRU-K 缓存机制。
输入格式：
输入第一行给出 3 个正整数：K（1<K≤5）、N (≤10^4 ) 和 M (≤10 ^5)，分别为规定的缓存命中次数、队列的大小（假设历史访问队列和缓存队列的大小一致）和被调用的数据的数量。随后一行给出 M 个被调用的数据的编号。编号为区间 [1,2×10 ^4] 内的一个整数。一行中的数字以空格分隔。
输出格式：
在第一行中输出历史访问队列中数据的编号。第二行输出缓存队列中数据的编号。顺序为队头至队尾。数据间以 1 个空格分隔，行首尾不得有多余空格。如果队列为空则输出 – 表示空行。
输入样例 1：
2 5 17
9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6 9
输出样例 1：
4 9
8 3 7 5 6
输入样例 2：
3 5 10
9 5 6 7 8 3 8 9 5 9
输出样例 2：
7 3 8 5 9
–
代码长度限制
16 KB
Java (javac)
时间限制
900 ms
内存限制
256 MB
其他编译器
时间限制
200 ms
内存限制
64 MB
开始想用一个大数组分别存储历史访问队列和缓存队列，但是好像把题意理解错了，然后得了1分。改了一会后得了3分。这题真的坑，1个多小时的时候看一个大佬17分。整的我很紧张。当时GPT那题没AC(qaq).
最后换了种方法，可惜list的运用不熟练，最后写了一堆bug.现在补一下，估计过的应该多几分。
下面这个代码为了看清过程，加了点私货。
思路：首先整个结构体用于记录选中次数。list(his)作为历史访问队列，list(sto)作为缓存队列.
因为会清除最长时间没有被使用过的数据，所以输入一个数：
先判断是否在缓存中，如果在，将其移到缓存队列尾端，不在，判断是否在历史访问队列中。
在历史访问的话，将其次数加一，达到k移到缓存中，(不到k要移到历史访问队列尾端)
不在的话，次数置为1然后加到历史访问队列中。
（添加的时候要判断是否超过队列长度，超过的话，移除队首元素）
单纯的补下题，感觉思路有问题的话，希望大家能讨论下。
网上也找不到，好想提交试一下。。。
样例
#include<bits/stdc++.h>
using namespace std;
int k,n,m;
struct h{
int date;
int rel;
}c;
list<h> his;
list<int> sto;
list<h>::iterator p,P;
list<int>::iterator l,L;
list<int>::iterator findsto(int x){//在缓存队列中寻找数据
for(l=sto.begin();l!=sto.end();++l){
if(x==*l) return l;
}
return sto.end();
}
list<h>::iterator findhis(h x){//在历史访问队列中寻找数据
for(p=his.begin();p!=his.end();++p){
if(x.date==p->date) return p;
}
return his.end();
}
void wxf(){
cout<<"历史数据： ";
int rel=n;
for(p=his.begin();p!=his.end();++p){
cout<<p->date<<" ";
--rel;
}
while(rel--){
cout<<" ";
}
cout<<"缓存数据： ";
for(l=sto.begin();l!=sto.end();++l){
cout<<*l<<" ";
}
if(sto.empty()){
for(int i=0;i<n;++i)
cout<<"--";
}
cout<<endl;
}
int main(){
cin>>k>>n>>m;
while(m--){
int num;
scanf("%d",&num);
L=findsto(num);
if(L!=sto.end()){//数据在缓存里
l=L;
sto.erase(L);
sto.push_back(num);
}
else{//数据不在缓存里
c.date=num;
p=findhis(c);
if(k==1){
sto.push_back(num);
if(sto.size()==n+1) sto.pop_front();
}
if(p!=his.end()){//数据在历史记录里
p->rel+=1;
if(p->rel==k){//命中k次
his.erase(p);
sto.push_back(num);
if(sto.size()==n+1) sto.pop_front();
wxf();
continue;
}
c=*p;
his.erase(p);
his.push_back(c);
p=findhis(c);
}
else{//数据不在历史数据里
c.rel=1;
his.push_back(c);
if(his.size()==n+1) his.pop_front();
}
}
wxf();
}
return 0;
}
//2 5 16
//9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6
//2 5 17
//9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6 9
//3 5 10
//9 5 6 7 8 3 8 9 5 9