P1540 [NOIP 2010 提高组] 机器翻译

难度： 普及−
标签： 模拟、队列、FIFO、NOIP
来源： 洛谷 P1540

题目背景

本题来源于 NOIP 2010 提高组第一题。

题目背景

本题围绕“[NOIP 2010 提高组] 机器翻译”所描述的场景展开。一款机器翻译软件从文章开头到结尾逐个翻译英文单词。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

题目描述

一款机器翻译软件从文章开头到结尾逐个翻译英文单词。每遇到一个单词，软件先在内存中查找：

• 若该单词已经在内存中，直接使用，不访问外存词典；
• 若该单词不在内存中，就访问一次外存词典完成翻译，并把该单词及其译义存入内存。

内存共有 $M$ 个单元，每个单元只能保存一个单词及其译义。当内存尚未装满时，新单词存入空闲单元；当内存已经保存了 $M$ 个单词时，先删除最早进入内存的那个单词，再把新单词存入。因此替换规则是先进先出。

给定一篇包含 $N$ 个单词的文章。开始翻译前内存为空，请计算翻译整篇文章需要访问外存词典多少次。

完整规则与任务要求

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

• 一款机器翻译软件从文章开头到结尾逐个翻译英文单词。
• 每遇到一个单词，软件先在内存中查找：。
• 若该单词已经在内存中，直接使用，不访问外存词典；。
• 若该单词不在内存中，就访问一次外存词典完成翻译，并把该单词及其译义存入内存。
• 内存共有 $M$ 个单元，每个单元只能保存一个单词及其译义。
• 当内存尚未装满时，新单词存入空闲单元；。
• 当内存已经保存了 $M$ 个单词时，先删除最早进入内存的那个单词，再把新单词存入。
• 因此替换规则是先进先出。
• 只有不在内存中的单词才访问外存并计数。
• 内存满时删除最早进入、且仍在内存中的单词，替换策略为 FIFO。

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入格式

共两行：

• 第一行输入两个正整数 $M,N$，分别表示内存容量和文章单词数；
• 第二行输入 $N$ 个非负整数，按照文章中的出现顺序给出。每个整数不超过 $1000$，相同整数表示相同单词，不同整数表示不同单词。

同一行相邻整数之间用一个空格分隔。

输出格式

输出一个整数，表示访问外存词典的总次数。

输入输出样例

3 7
1 2 1 5 4 4 1

5

样例说明

内存变化如下：

1. 单词 $1$ 不在内存，查词典并加入，内存为 1；
2. 单词 $2$ 不在内存，查词典并加入，内存为 1 2；
3. 单词 $1$ 已存在，不查词典；
4. 单词 $5$ 不在内存，查词典并加入，内存为 1 2 5；
5. 单词 $4$ 不在内存，删除最早加入的 $1$，再加入 $4$，内存为 2 5 4；
6. 单词 $4$ 已存在，不查词典；
7. 单词 $1$ 不在内存，删除最早加入的 $2$，再加入 $1$，内存为 5 4 1。

总共访问词典 $5$ 次。

数据范围

• 对于 $10\%$ 的数据：$M=1$，$N\le 5$；
• 对于全部数据：$1\le M\le 100$，$1\le N\le 1000$；
• 单词编号范围为 $0$ 到 $1000$。

边界与子任务说明

• 测试数据可能覆盖题面允许的最小值、最大值、重复值、空结果、无解或极端结构等边界情形。
• 若原题未额外列出分档子任务，则所有测试点统一遵守上述完整数据范围；若题面已经列出比例或分档条件，则这些条件均应视为题面的一部分。
• 不能根据公开样例推断未写出的额外限制。

本题面依据洛谷 P1540 的公开题目信息重新整理，为内容完整的非逐字重述版。