例题-机器翻译

题目大意

内存中有 \(M\) 个单元，每个单元可以存储一个单词和其意译。

现有 \(N\) 个单词，刚刚开始内存空间是空的，什么都单词和其意译都没有存，每读取一个新单词时就会上网搜索该单词的含义，并将其存进内存空间中，若下次再遇到该单词并且还在内存空间中的话，就不用上网再搜一遍。

若单词太多的话，内存空间不够用，此时就要将最早放入内存中的单词和其意译删除掉，腾出一个新空间放入内存中。

请问该机器要上网搜多少次才能将这些单词翻译完毕？

输入格式

第一行输入两个整数，分别代表 \(M、N\)；

第二行输入 \(N\) 个整数，每个整数都代表一个单词，当两个整数的数值相同时，这两个整数代表的单词也相同。

输出格式

输出一个整数代表上网搜索的次数。

数据范围

\(1 \leq M \leq 100\)

\(1 \leq N \leq 1000\)

每个单词所对应的整数 \(\in [0, 1000]\)

思路

定义一个数组 a[i] 代表单词 i 是否存在队列中，若 a[i] = 1 说明单词 i 存在队列中，否则就不存在队列中，此时就要将其存入队列中，并且查找次数要递增 \(1\)。

代码参考

#include <iostream>
#include <queue>

using namespace std;
const int N = 1e7 + 10;

int a[N], t, n, m, res;
queue<int> qa;

int main(void)
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++) 
    {
        cin >> t;
        if (!a[t]) 
        {
            a[t] = 1, res ++;
            if (qa.size() == m) 
            {
                a[qa.front()] = 0; qa.pop();
            }
            qa.push(t);
        }
    }
    cout << res << endl;

    return 0;
}