[NOIP 2010 提高组] 机器翻译

GitHub跳转原题关系图返回列表

用队列维护单词进入内存的先后顺序，再用标记数组判断当前是否命中内存。

OJ: luogu

题目 ID: P1540

难度:普及-

标签:队列模拟noippython

日期: 2026-06-18 14:16

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

有一篇文章，按顺序给出 N 个单词编号。

翻译软件的内存最多只能存 M 个单词：

  • 如果当前单词已经在内存里，就直接使用，不查词典；
  • 如果不在内存里，就要查一次词典，并把它放入内存；
  • 如果内存已满，就删掉最早进入内存的那个单词，再把新单词放进去。

要求统计总共查了多少次词典。

思路

先看一个最朴素的模拟：直接用数组保存当前内存中的单词。

每次读到一个单词，就在线性扫描数组里找它是否已经存在；如果不存在，答案加一，必要时删掉数组最前面的单词，再把当前单词放到数组末尾。

这个写法直观、容易验证：

cpp
#include <bits/stdc++.h>
using namespace std;

int m, n;
int x;
int ans;
vector<int> memory_words;

bool exists_in_memory(int word) {
    for (int v : memory_words) {
        if (v == word) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;

    for (int i = 1; i <= n; i++) {
        cin >> x;

        if (exists_in_memory(x)) {
            continue;
        }

        ans++;
        if ((int) memory_words.size() == m) {
            memory_words.erase(memory_words.begin());
        }
        memory_words.push_back(x);
    }

    cout << ans << '\n';
    return 0;
}

不过它每次都要在线性扫描当前内存，不够干净。

题目真正的结构其实很明确：

  • 新单词进入内存时，总是放到最后面；
  • 内存满了时，总是删掉最早进入内存的单词。

这正是队列的先进先出模型。

所以我们可以：

  • 用队列保存“当前内存里的单词进入顺序”；
  • 用 in_memory[x] 记录单词 x 当前是否已经在内存中。

这样每次处理一个单词时：

  • 若 in_memory[x] 为真，说明命中，直接跳过；
  • 否则答案加一；
  • 如果队列已满，先弹出队头并清除它的存在标记；
  • 再把新单词压入队尾。

这题也正好被 rbook 的《队列》文章列为基础队列模拟例题： https://rbook2.roj.ac.cn/data-structure/queue/index.html

Python 知识

  • deque 维护 FIFO 淘汰顺序，set 维护当前是否命中；两种容器各负责一种操作。
  • word in memory 平均 O(1)O(1)，避免每次扫描整个队列。
  • 淘汰时 memory.remove(order.popleft()) 把队首值直接从集合中同步删除。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 判重与 deque 队列。

代码

python
import sys
from collections import deque


data = list(map(int, sys.stdin.buffer.read().split()))
capacity, word_count = data[:2]
words = data[2:2 + word_count]
memory = set()
order = deque()
lookups = 0

for word in words:
    if word in memory:
        continue
    lookups += 1
    if len(order) == capacity:
        memory.remove(order.popleft())
    order.append(word)
    memory.add(word)

print(lookups)

复杂度

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(m)O(m)

总结

这题的关键是识别出“淘汰最早进入内存的单词”这一条规则。

一旦看出它是 FIFO 缓存，就可以自然地想到“队列维护顺序，标记数组维护是否存在”的做法。