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

[NOIP 2010 提高组] 机器翻译

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

题目描述

\hspace{15pt}小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。

\hspace{15pt}这个翻译软件的原理很简单:它从头到尾依次处理文章中的每个英文单词,把每个单词替换为对应的中文含义。

\hspace{15pt}对于每个英文单词,软件先在内存中查找这个单词的中文含义:

∙ \hspace{23pt}\bullet\,如果内存中有这个单词,就直接用内存中的含义进行翻译,不需要去查找词典;

∙ \hspace{23pt}\bullet\,如果内存中没有这个单词,就去外存中的词典内查找它的中文含义,完成翻译,并把这个单词和它的含义放入内存,以备后续使用。

\hspace{15pt}假设内存中有 mm 个单元,每个单元能存放一个单词和它的含义。每当软件要将一个新单词存入内存时:

∙ \hspace{23pt}\bullet\,若内存中已存入的单词数量不超过 m−1m-1,就把新单词存入一个尚未使用的单元;

∙ \hspace{23pt}\bullet\,若内存中已存入 mm 个单词,就先清空最早进入内存的那个单词、腾出单元,再存放新单词。

\hspace{15pt}假设这篇英语文章的长度为 nn 个单词,并且翻译开始前内存中没有任何单词。请你求出翻译软件需要去外存查找多少次词典。

输入格式

\hspace{15pt}第一行输入两个整数 mm 和 $n \left(1 \leqq m \leqq 100;\ 1 \leqq n \leqq 1000\right)$ 分别代表内存的容量和文章的长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 1000\right)$,按照文章的顺序给出每个单词的编号。其中 aia_i 代表文章中第 ii 个单词的编号;两个单词是同一个单词,当且仅当它们对应的编号相同。

输出格式

\hspace{15pt}在一行上输出一个整数,代表翻译软件需要去外存查找词典的次数。

测试样例

3 7
1 2 1 5 4 4 1
5

样例 1 解释

\hspace{15pt}内存容量为 m=3m=3,文章共有 n=7n=7 个单词。依次处理每个单词,下面的括号中是处理完该单词后内存里的单词,按进入内存的先后顺序书写:

∙ \hspace{23pt}\bullet\,第 11 个单词 11:内存中没有,查找词典,内存变为 {1}\{1\};

∙ \hspace{23pt}\bullet\,第 22 个单词 22:内存中没有,查找词典,内存变为 {1,2}\{1,2\};

∙ \hspace{23pt}\bullet\,第 33 个单词 11:内存中有,不需要查找词典,内存仍为 {1,2}\{1,2\};

∙ \hspace{23pt}\bullet\,第 44 个单词 55:内存中没有,查找词典,内存变为 {1,2,5}\{1,2,5\};

∙ \hspace{23pt}\bullet\,第 55 个单词 44:内存中没有,此时内存已满,清空最早进入的单词 11 后查找词典,内存变为 {2,5,4}\{2,5,4\};

∙ \hspace{23pt}\bullet\,第 66 个单词 44:内存中有,不需要查找词典,内存仍为 {2,5,4}\{2,5,4\};

∙ \hspace{23pt}\bullet\,第 77 个单词 11:内存中没有,清空最早进入的单词 22 后查找词典,内存变为 {5,4,1}\{5,4,1\}。

\hspace{15pt}其中第 1,2,4,5,71,2,4,5,7 个单词需要查找词典,共计 55 次,因此输出 55。

2 6
1 2 1 3 1 2
5

提示

\hspace{15pt}对于 10%10\% 的数据,m=1m=1,n≦5n \leqq 5;

\hspace{15pt}对于 100%100\% 的数据,1≦m≦1001 \leqq m \leqq 100,1≦n≦10001 \leqq n \leqq 1000。

\hspace{15pt}本题为 NOIP 2010 提高组 T1。