#include <bits/stdc++.h>
#define ll long long
using namespace std;
queue<int> q;
int f[1005],m,n,x,ans;
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(!f[x]){
            ans++;
            q.push(x);
            f[x]=1;
            if(q.size()>m)
                f[q.front()]=0,q.pop();
        }
    }
    cout<<ans;
    return 0;
}

注：本题解使用的是STL队列

题意&思路

输入 $n$ 个数，每输入一个就判断：

• 如果序列中已有这个数，那么不用再加入序列；
• 否则如果序列中元素个数 $< m$，直接将它加入序列；
• 否则删除当前序列中最先加入的那个元素，并把输入的数加入序列。

最后输出往序列中加入元素的总次数。

根据上述分析可以使用队列来解决，其余的模拟即可。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1005;
ll m,n,ans;
bool flag[N];
queue<ll> q;
int main(){
    scanf("%lld%lld",&m,&n);
    for(ll i=1,x;i<=n;i++){
        scanf("%lld",&x);
        if(!flag[x]){ // 如果序列中没有这个数（单词）
            ans++,flag[x]=1; // 将总次数+1，并标记为这个数出现过
            if(q.size()==m) // 如果队列已满
                flag[q.front()]=0,q.pop(); // 删除队首并移除标记
            q.push(x); // 加入队列
        }
    }
    printf("%lld",ans);
    return 0;
}

算法分析：

用队列先进先出的特性模拟内存存放单词；用一个一维数组标记某一个单词是否在于内存中以便快速确定是否需要查找词典。其余的基本就是纯粹模拟了。

有一点需要注意：若是使用循环队列，需要好好检查循环队列中元素个数的计算是否正确。

代码一：不使用循环队列，直接把队列定义得足够大

#include<stdio.h>
#define maxQueueLength 1005
int main()
{
    int M,N;
    int que[maxQueueLength]={0},check[1005]={0}; // que[]是循环队列，用来模拟内存；check[i]==1表示i在内存中。
    int ans=0,begin,end,i,t;
    scanf("%d%d",&M,&N);

    begin=end=0;//初始化队列
    for(i=0;i<N;i++)
    {
        scanf("%d",&t);
        if(check[t]==0)//查找内存，发现内存中没有t存在
        {
            ans++;//查找字典的次数增加一次
            //现在开始做单词放进内存的过程
            if(end-begin<M)
            {
                que[end++]=t;
            }
            else //end-begin>=M
            {
                check[que[begin]]=0;
                begin++;
                que[end++]=t;
            }
            check[t]=1;//标记t已经在内存中
        }
    }
    printf("%d\n",ans);
    return 0;
}

代码二：使用循环队列，节省一些队列空间

#include<stdio.h>
#define maxQueueLength 105
int main()
{
    int M,N;
    int que[maxQueueLength]={0},check[1005]={0}; // que[]是循环队列，用来模拟内存；check[i]==1表示i在内存中。
    int ans=0,begin,end,i,t,count;

    scanf("%d%d",&M,&N);

    begin=end=0;//初始化队列
    for(i=0;i<N;i++)
    {
        scanf("%d",&t);
        if(check[t]==0)//查找内存，发现内存中没有t存在
        {
            ans++;//查找字典的次数增加一次
            //现在开始做单词放进内存的过程
            if(end>=begin) count=end-begin;
            else count=maxQueueLength-begin+end;

            if(count<M)
            {
                que[end++]=t;
                if(end>=maxQueueLength) end=end%maxQueueLength;
            }
            else //end-begin>=M
            {
                check[que[begin]]=0;
                begin++;
                que[end++]=t;
                if(begin>=maxQueueLength)begin=begin%maxQueueLength;
                if(end>=maxQueueLength)end=end%maxQueueLength;
            }
            check[t]=1;//标记t已经在内存中
        }
    }
    printf("%d\n",ans);
    return 0;
}