算法

(模拟，队列) $O(N)$

这道题是让我们实现一个先进先出的缓存机制。

数据的存储：

1. 由于是先进先出，所以我们可以用循环队列来维护缓存中的所有单词，这里可以用C++STL中的queue。
2. 用bool数组存储每个单词是否已经在队列中，这样就可以用 $O(1)$ 的时间判断每个单词是否已在缓存中了。

从前往后依次处理文章中的每个单词，然后分情况处理：

• 如果 $x$ 已在缓存中，不需要做其他处理；
• 如果 $x$ 不在缓存中：
  • 如果队列不满，将 $x$ 插入队尾；
  • 如果队列已满，将队头弹出，然后将 $x$ 插入队尾；

时间复杂度分析

依次对每个单词处理一遍，每次处理时只有常数次操作，所以总时间复杂度是 $O(N)$，其中 $N$ 是单词个数。

C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1010;

int m, n;
bool st[N];

int main()
{
    cin >> m >> n;

    queue<int> q;
    int res = 0;

    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        if (!st[x])
        {
            if (q.size() == m)
            {
                int t = q.front();
                st[t] = false;
                q.pop();
            }

            q.push(x);
            st[x] = true;
            res ++ ;
        }
    }

    cout << res << endl;
    return 0;
}