[NOIP 2010 提高组] 机器翻译

知识点

模拟、队列、缓存

解题思路

队列保存单词进入缓存的先后顺序，布尔数组标记是否在缓存。命中时不改变顺序；未命中则计数，若已满就移除队首，再加入新词。

正确性说明

队列与标记数组始终表示当前内存。题目在未命中时淘汰最早进入者，与队首一致；命中不重新进入内存，故保持队列顺序。归纳得到每次查词典计数正确。

易错点

命中不能移到队尾；M=1也适用；词编号允许0；不同单词按数值判断。

复杂度

时间O(N)，空间O(M+1001)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int m,n;cin>>m>>n;queue<int>q;bool has[1001]={};int ans=0;while(n--){int x;cin>>x;if(has[x])continue;++ans;if((int)q.size()==m){has[q.front()]=false;q.pop();}q.push(x);has[x]=true;}cout<<ans<<'\n';}