首页 > 试题广场 >

机器翻译

[编程题]机器翻译

热度指数：2785 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 牛牛的电脑上安装了一个机器翻译软件，它依次将每个英文单词替换为对应的中文含义。软件内部有 $M$ 个缓存单元，每个单元存放一个单词和译义。翻译某个单词时：
$\hspace{23pt}\bullet\,$ 如果缓存中已有该单词，则直接使用（缓存命中）；
$\hspace{23pt}\bullet\,$ 否则需要到外存词典查找（缓存未命中），并将该单词及译义插入缓存：若缓存未满，则占用一个空闲单元；若缓存已满，则清除最早进入缓存的单词后插入新单词。
$\hspace{15pt}$ 给定长度为 $N$ 的文章（由 $N$ 个整数编码表示单词），初始缓存为空，统计翻译过程中需要查词典的次数。

输入描述:

第一行输入两个整数 （，），分别表示缓存容量和文章单词数。
第二行输入  个整数 （），表示文章中按顺序出现的单词编码。

输出描述:

输出一个整数，表示翻译过程中缓存未命中（查词典）的总次数。

示例1

输入

3 7
1 2 1 5 4 4 1

输出

说明

翻译过程示例（缓存状态记录自左向右为最早到最近）：
初始：空
1: miss，缓存->[1]
2: miss，缓存->[1,2]
1: hit，缓存->[1,2]
5: miss，缓存->[1,2,5]
4: miss，缓存->[2,5,4]（替换1）
4: hit，缓存->[2,5,4]
1: miss，缓存->[5,4,1]（替换2）
共 miss 5 次。