LG#P1540. [NOIP 2010 提高组] 机器翻译
[NOIP 2010 提高组] 机器翻译
P1540 [NOIP 2010 提高组] 机器翻译
题目描述
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单:它从头到尾依次处理文章中的每个英文单词,把每个单词替换为对应的中文含义。
对于每个英文单词,软件先在内存中查找这个单词的中文含义:
如果内存中有这个单词,就直接用内存中的含义进行翻译,不需要去查找词典;
如果内存中没有这个单词,就去外存中的词典内查找它的中文含义,完成翻译,并把这个单词和它的含义放入内存,以备后续使用。
假设内存中有 个单元,每个单元能存放一个单词和它的含义。每当软件要将一个新单词存入内存时:
若内存中已存入的单词数量不超过 ,就把新单词存入一个尚未使用的单元;
若内存中已存入 个单词,就先清空最早进入内存的那个单词、腾出单元,再存放新单词。
假设这篇英语文章的长度为 个单词,并且翻译开始前内存中没有任何单词。请你求出翻译软件需要去外存查找多少次词典。
输入格式
第一行输入两个整数 和 $n \left(1 \leqq m \leqq 100;\ 1 \leqq n \leqq 1000\right)$ 分别代表内存的容量和文章的长度。
第二行输入 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 1000\right)$,按照文章的顺序给出每个单词的编号。其中 代表文章中第 个单词的编号;两个单词是同一个单词,当且仅当它们对应的编号相同。
输出格式
在一行上输出一个整数,代表翻译软件需要去外存查找词典的次数。
测试样例
3 7
1 2 1 5 4 4 1
5
样例 1 解释
内存容量为 ,文章共有 个单词。依次处理每个单词,下面的括号中是处理完该单词后内存里的单词,按进入内存的先后顺序书写:
第 个单词 :内存中没有,查找词典,内存变为 ;
第 个单词 :内存中没有,查找词典,内存变为 ;
第 个单词 :内存中有,不需要查找词典,内存仍为 ;
第 个单词 :内存中没有,查找词典,内存变为 ;
第 个单词 :内存中没有,此时内存已满,清空最早进入的单词 后查找词典,内存变为 ;
第 个单词 :内存中有,不需要查找词典,内存仍为 ;
第 个单词 :内存中没有,清空最早进入的单词 后查找词典,内存变为 。
其中第 个单词需要查找词典,共计 次,因此输出 。
2 6
1 2 1 3 1 2
5
提示
对于 的数据,,;
对于 的数据,,。
本题为 NOIP 2010 提高组 T1。