题解 | 机器翻译

#include <iostream>
#include <queue>
using namespace std;
/*
代码思路：
如果输入的单词不存在小本本里，就查词典记录在小本本，如果小本本满了就删除最先记录的单词。如果在小本本就啥也不操作，关键词为“删除最先记录”，符合队列先进先出原则。
用一个队列维护小本本，关键是如何遍历小本本来确认新输入的单词是否已经存在。
可以用一个临时变量，复制当前的小本本，然后通过操作小本本的副本不断出队来完成遍历和判断。为此我们可以写一个判断函数，如果新词存在就返回true，不存在就返回false。在函数外部，处理miss的情形，如果单词满了就出队，然后添加新单词。
*/
// 判断函数，用于判断输入的新单词是否在单词本
bool check_dict(queue<int>& dict, int w) {
    queue<int> tem = dict;  // 建立副本，如果不传引用，就不需要申明tem，直接用dict即可
    while (!tem.empty()) {  // 直到为空或提前返回值才停止循环
        int dict_word = tem.front();
        tem.pop();
        if (w == dict_word) return true;  // 如果找到就提前返回
    }

    return false;  // 没找到就返回false
}

int main() {
    int M, N;       // M单词本最大容量， N单词数目
    cin >> M >> N;  // 先把数据收进来
    queue<int> que;
    int times_ = 0;  // 记录查字典的总数
    int word;  // 第一个单词肯定没有，直接入队
    cin >> word;
    // 第一个单词必miss
    que.push(word);
    times_++;
    N--;
    while (N--) {  // 判断剩余单词
        cin >> word;  // 把单词收进来
        // 判断是否需要查词典
        if (!check_dict(que, word)){  // 如果函数返回false代表单词本里面没有这个单词
            times_++;  // 需要查字典
            // 处理miss
            if (que.size() >= M) { // 如果
                que.pop();
            }
            que.push(word);
        } 
    }
    cout <<  times_;
}


// 64 位输出请用 printf("%lld")