机器翻译（洛谷P1540）
题目大意
有m个可存放单词和译意的单元，初始内容为空，依次读取文章单词，若在内存单元中不存在则从外存读入，载入内存，若内存数据超过m则最先录入内存单元的出队，直到文章全部翻译完，求外存查找次数。
解题思路
限定了队列容量为m，每当队列中找不到匹配单词时从外存载入，次数+1，超过队列容量时，依据队列FIFO原则。
STL queue
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
bool vis[N]; //记录是否在队列中，降低时间复杂度
int main(){
int n,m;
cin>>n>>m;
queue<int>q;
int ans=0;
for(int i=1,k;i<=m;i++){
cin>>k;
if(!vis[k]){
q.push(k);
ans++;
if(q.size()>n){ //超出容量出队
vis[q.front()]=false; //标记
q.pop();
}
}
vis[k]=true;
}
cout<<ans<<endl;
return 0;
}
手写循环队列
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
bool vis[N];
struct myque{
int v[N];
/*动态分配 int*v; */
int head,rear;
bool init(){
/*动态分配
v=(int*)malloc(N*sizeof(int);
if(!v)return false; */
head=rear=0;
return true;
}
int size(){
return (rear-head+N)%N;
}
bool empty(){
return size()==0;
}
bool push(int x){
if((rear+1)%N==head)return false; //队列满
v[rear]=x;
rear=(rear+1)%N;
return true;
}
bool pop(int&x){
if(head==rear)return false; //队列空
x=v[head];
head=(head+1)%N;
return true;
}
int front(){
return v[head];
}
}Q;
int main(){
Q.init();
int n,m;
cin>>n>>m;
int ans=0;
for(int i=1,k;i<=m;i++){
cin>>k;
if(!vis[k]){
ans++;
vis[k]=true;
Q.push(k);
if(Q.size()>n){
int ret;
Q.pop(ret);
vis[ret]=false;
}
}
}
cout<<ans<<endl;
return 0;
}
滑动窗口/单调队列（洛谷P1886）
题目大意
有n个人，编号为1~n，初始队列为1号一个人，入队方式为指定插入编号i同学的左边或右边，删去m个同学，求剩余队列同学的编号
解题思路
对链表查找，添加，删除，遍历的操作。考虑遍历查找时间复杂度为O(n)，使用数组存储编号对应链表节点位置的迭代器，实现O(1)级别查找。
未知的代码
#include<bits/stdc++.h>
using namespace std;
#define ITER list<int>::iterator
const int N=1e5+5;
ITER pos[N]; //记录编号对应的链表节点
list<int>l;
bool vis[N]; //记录是否删除
int main(){
int n,m,k,p;
cin>>n;
l.push_back(1);
pos[1]=l.begin();
auto insert=[&](int k,int p,int v){
if(p)pos[v]=l.insert(next(pos[k]),v); //p==1,右插，迭代器+1
else pos[v]=l.insert(pos[k],v);
};
for(int i=2;i<=n;i++){
cin>>k>>p;
insert(k,p,i);
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>k;
if(!vis[k])l.erase(pos[k]);
vis[k]=true;
}
for(auto&it:l)cout<<it<<" ";
return 0;
}