这道题能出现在提高组还是算比较简单的了，整体算法就是一个简单的队列，分析一下——

其实这个题的思路本身就不算复杂，本蒟蒻第一次提交就得了30分100分。

我使用队列是因为我看到了“软件会清空最早进入内存的那个单词”这句话。

其实我们可以将整个内存看成一个先进先出的队列，存入就在队尾增加，删除就在队首删除。

最后再建一个变量，用于统计存入的次数——

换言之，就是共入队几次，答案就是几~

别问我为什么没用手动队列，我很严肃的告诉你:

因为——

我懒，

我想给大家复习一下队列的用法！

上正文：

#include<bits/stdc++.h>
using namespace std;
queue<int> q;						  //创建队列用于模拟内存 
int m,n,x,a;
bool book[1005];				 	  //book数组用于标记该单词是否已加入内存 
void z(){
	scanf("%d%d",&m,&n); 
	for(int i=1;i<=n;i++){
		scanf("%d",&x);				  //输入单词编号x 
		if(book[x])continue;		  //判断单词x是否在内存中 
		else{
			if(q.size()>=m){		  //判断内存是否溢出 
				book[q.front()]=false;//取消最早存入内存单词的标记 
				q.pop();			  //删除最早存入内存的单词 
			}
			q.push(x);				  //将新单词加入队尾 
			book[x]=true;			  //标记新单词 
			a++;					  //次数增加 
		}
	}
	printf("%d",a);
	return;							  //返回主函数 
}
int main(){
	z();							  //不要在意，个人习惯，个人不习惯在主函数里写程序 
	return 0;						  //记住加这句，不然比赛的时候会错 
}

该代码时间复杂度为 $O(n)$

代码已 AC。

请放心食用

相见就是缘分呀~

如果你看到了，不妨留下个赞再走呗，感谢观看~

886~

算法分析：哈希，指针。

解题思路：题目中的M个单元我们可以用一个bool类型的数组，a[i]用来记录i是否在单元里面，用int 类型b[]来记录数据的顺序，再用两个变量指向b[]的头和尾。

时间复杂度：O(n)

代码部分：

不能抄题解
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,l,r,b[1001];    不能抄题解//b[1001] 记录单词顺序 
bool a[i];
int main(){
    cin>>m>>n;
    for(int x,i=1;i<=n;i++){
        cin>>x
        if(a[x]==0){          不能抄题解//判断是否在单元里 
            an++;
            r++;
            b[r]=x;
            a[x]=1;
            if(r>m){          不能抄题解//判断是否超出单元数量 
                l++;
                a[b[l]]=0;
            }
        }
    }
    cout<<anss;
    return 0;
不能抄题解
此题解中有许多防止抄代码的陷阱，请谨慎食用