P4853 机器翻译(NOIP)（基础）

解题思路

第一步，理解题意。 翻译软件有一个内存，里面有 M 个单元，每个单元能放一个单词。翻译一篇文章时，每遇到一个单词：如果内存里已经有这个单词，就直接翻译，不用查词典；如果内存里没有，就要去外存的词典里查一次，然后把这个单词放进内存。内存满了 M 个单词时，会清掉"最早进入"的那个单词，腾出位置放新单词。问整个文章翻译下来，一共查了几次词典。

第二步，类比生活。 就像你书包里只能装 M 本小词典。看书遇到不认识的单词，先翻书包：书包里有就直接用；没有就去书架找（算一次"查词典"），找到后放进书包。书包装满了，就把最旧的那本拿出来再装新的。

第三步，用队列模拟内存。 队列"先进先出"，正好符合"最早进入的先被清掉"的规则。用数组 q 当队列，队首 head 指向最早进入的单词，队尾 tail 指向新单词放的位置。再用一个标记数组 in[]，in[x]=1 表示单词 x 现在在内存里（单词大小不超过 1000，数组开 1005 就够）。

第四步，逐个单词处理。 读入文章的第 x 个单词：如果 in[x]==1，说明内存里有，直接跳过；否则查词典次数加 1，然后看内存：如果没满（tail-head < M），直接把 x 放到队尾；如果满了，就把队首的单词清掉（in[q[head]]=0，head 加 1），再把 x 放到队尾。用一个变量 ans 累加查词典次数，最后输出 ans。

第五步，边界情况。 M 最小是 1，内存只有一个单元，每来一个新单词都要把旧的踢掉；连续出现相同的单词时，第二次就不查词典了。举个例子：M=3，文章是 1 2 1 5 4 4 1。过程是：查 1、查 2、1 在内存、查 5、查 4（内存满踢掉 1）、4 在内存、查 1（踢掉 2），总共查 5 次，和样例一致。

参考代码

// 机器翻译(NOIP)：内存M个单元，FIFO缓存，统计查词典次数
#include <iostream>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    int q[1005];          // 内存队列，按存入顺序存放单词
    int in[1005] = {0};   // in[x]=1 表示单词 x 已在内存
    int head = 0, tail = 0;
    int ans = 0;          // 查词典次数
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (in[x]) continue;    // 内存有，不用查词典
        ans++;                  // 内存没有，去词典查
        if (tail - head < m) {  // 内存还没满
            q[tail++] = x;
            in[x] = 1;
        } else {                // 内存已满，清掉最早进入的
            in[q[head]] = 0;
            head++;
            q[tail++] = x;
            in[x] = 1;
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度：每个单词只处理一次，所以是 O(N)，N 最大和文章长度相同，非常高效。

空间复杂度：队列长度不超过 M，标记数组大小取决于单词最大值（不超过 1000），所以是 O(M + 1000)。