机器翻译

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

FIFO 缓存模拟：按顺序处理单词，命中直接翻译，未命中查词典一次并淘汰最早进入的单词。

OJ: roj

题目 ID: 1401

难度:普及-

标签:模拟队列python

创建: 2026-09-30 08:46

更新: 2026-10-05 12:53

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

内存容量 MM，文章长度 NN。依次处理每个单词：内存中有则直接翻译；没有则查一次词典并放入内存，若内存已满则淘汰最早进入的单词。求查词典次数。单词为非负整数（≤1000）。

思路

用数组模拟 FIFO 队列，再用一个标记数组 inq[1005] 做 O(1)O(1) 命中判断。未命中时计数 +1，满则队首出队，新单词入队尾。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from collections import OrderedDict


def solve() -> None:
    """模拟 FIFO 缓存：内存未命中则查词典一次，并淘汰最早进入的单词。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)          # 内存容量、单词个数
    words = [next(data) for _ in range(n)]  # N 个单词，按输入顺序顺序消费

    cache: OrderedDict[int, None] = OrderedDict()  # 按进入内存的顺序存放单词
    lookups = 0                                     # 查外存词典的次数
    for w in words:
        if w in cache:                              # 内存命中，直接翻译
            continue
        lookups += 1                                # 未命中：查一次外存词典
        if len(cache) == m:                         # 内存已满，淘汰最早进入的
            cache.popitem(last=False)
        cache[w] = None                             # 新单词进入内存（队尾）
    print(lookups)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:53
 * update_at: 2026-10-05 12:53
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 105;

int m, n;
int q[MAXM];      // 队列：按进入顺序存放内存中的单词，队首为最旧
int head, tail;   // 队首、队尾指针（[head, tail)）
int inq[1005];    // inq[x] = 1 表示单词 x 当前在内存中（单词值不超过 1000）

// 判断单词 w 是否在内存中
bool find(int w) {
    return inq[w];
}

// 将单词 w 调入内存：若已满则淘汰队首最早进入的单词
void insert(int w) {
    if (tail - head == m) {   // 内存已满
        inq[q[head]] = 0;     // 淘汰队首
        head++;
    }
    q[tail++] = w;            // 新单词入队尾
    inq[w] = 1;
}

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

    cin >> m >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int w;
        cin >> w;
        if (find(w)) continue; // 内存命中，直接翻译
        ans++;                  // 未命中：查一次外存词典
        insert(w);              // 调入内存
    }
    cout << ans << "\n";
    return 0;
}