[NOIP2010 提高组] 机器翻译
2024-10-20 15:49:56
问题描述
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有M个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为N个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
输入
输入文件共2行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M和N,代表内存容量和文章的长度。
第二行为N个非负整数,按照文章的顺序,每个数(大小不超过1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。
对于10%的数据有M = 1,N ≤ 5。
对于100%的数据有0 < M ≤ 100,0 < N ≤ 1000。
输出
共1行,包含一个整数,为软件需要查词典的次数。
样例输入
3 7
1 2 1 5 4 4 1
样例输出
1
代码如下
1 #include<iostream>
2 #include<queue>
3 using namespace std;
4 queue<int> q;//队列模拟内存情况
5 int m,n,ans;
6 bool inq[1010];//判断单词是否在内存中
7 int main()
8 {
9 cin>>m>>n;
10 for(int i=1;i<=n;i++)
11 {
12 int x;
13 cin>>x;
14 if(inq[x])continue;//能够在内存中查找就跳过
15 else
16 {
17 //如果内存满了,最早进入内存的那个单词出列
18 if(q.size()>=m)
19 {
20 inq[q.front()]=false;
21 q.pop();
22 }
23 //把外存的结果加入内存以便下次查找
24 q.push(x);
25 inq[x]=true;
26 ans++;
27 }
28 }
29 cout<<ans;
30 return 0;
31 }
最新文章
- 第一个Mac shell 小脚本
- 什么是UIScrollView
- Support Vector Machine (3) : 再谈泛化误差(Generalization Error)
- 对于Mybatis在C#.Net中个人使用的总结(一) Mybatis 的结果映射
- 链表——PowerShell版
- Javascript Design Patterns - Js Class
- Android 事件监听处理
- Otto Product Classification Winner&#39;s Interview: 2nd place, Alexander Guschin &#175;\_(ツ)_/&#175;
- free 命令解释
- Process.RedirectStandardInput
- linux串口驱动分析——打开设备
- UC/0S2之中断
- 配置zabbix agent向多个server发送数据
- [Swift]LeetCode928. 尽量减少恶意软件的传播 II | Minimize Malware Spread II
- centos7安装rabbitmq3.7.9
- eclipse 安装合适的pydev插件
- JAVA中的ZoneId常用值备注
- Maven之基本概念及特性的基本介绍
- jQuery插件初级练习4答案
- 机器学习中几种优化算法的比较(SGD、Momentum、RMSProp、Adam)