题解：机器翻译（FIFO缓存模拟）

一、解题核心思路

本题是FIFO（先进先出）缓存替换策略的模拟问题：内存容量为 $M$，遍历文章中的每个单词，若单词不在内存中则查词典（计数+1），并将单词加入内存；若内存已满，则移除最早加入的单词后再加入新单词。

核心数据结构选择：

• 队列：记录内存中单词的顺序（队首为最早加入的单词）；
• 集合：快速判断单词是否在内存中（O(1) 查找效率）。

二、具体解题步骤

1. 输入读取：读取内存容量 $M$、文章长度 $N$，以及 $N$ 个单词；
2. 初始化结构：用队列存内存中的单词（维护顺序），用集合存内存中的单词（快速查询），用计数器记录查词典次数；
3. 遍历单词：
   • 若单词在集合中：缓存命中，跳过；
   • 若单词不在集合中：
     • 查词典次数+1；
     • 若内存已满（队列大小等于 $M$）：移除队首单词（最早加入的），并从集合中删除；
     • 将当前单词加入队列和集合；
4. 输出结果：输出查词典的总次数。

三、完整代码实现

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;
    vector<int> words(N);
    for (int i = 0; i < N; ++i) {
        cin >> words[i];
    }

    queue<int> cache;          // 维护内存中单词的顺序（FIFO）
    unordered_set<int> exist;  // 快速判断单词是否在内存中
    int count = 0;             // 查词典次数

    for (int word : words) {
        if (exist.count(word)) {
            // 缓存命中，无需查词典
            continue;
        }
        // 缓存未命中，查词典
        count++;
        // 内存已满，移除最早加入的单词
        if (cache.size() == M) {
            int oldest = cache.front();
            cache.pop();
            exist.erase(oldest);
        }
        // 加入新单词到内存
        cache.push(word);
        exist.insert(word);
    }

    cout << count << endl;
    return 0;
}

四、代码解释

• 队列 cache：严格遵循先进先出规则，满员时优先删除队首（最早加入）的单词；
• 集合 exist：通过哈希表实现 O(1) 时间的存在性查询，避免数组遍历的低效；
• 核心逻辑：遍历每个单词，仅在未命中缓存时查词典，并维护内存的 FIFO 规则。

五、复杂度分析

• 时间复杂度：$O(N)$。每个单词的查找、插入、删除操作均为 O(1)，遍历 $N$ 个单词总时间为 O(N)；
• 空间复杂度：$O(M)$。队列和集合的最大大小为内存容量 $M$，空间开销可控。

该代码简洁高效，完美适配题目数据范围，能快速得到正确结果。