引用站外地址
P1540 [NOIP2010 提高组] 机器翻译
洛谷

前言

书接上文，本文同样转载自FZQOJ，因为大家学的比较基础，遂简单科普了队列。

略臭题目，话说这道题居然是提高组，€€￡的眼光不愧优秀。

这道题也是一个简单模拟题。需要用到队列。

题面

点击查看题面

题目背景

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

题目描述

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 MM 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1M-1，软件会将新单词存入一个未使用的内存单元；若内存中已存入 MM 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 NN 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 22 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 M,NM,N，代表内存容量和文章的长度。

第二行为 NN 个非负整数，按照文章的顺序，每个数（大小不超过 10001000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

样例 #1

样例输入 #1

1
2
3 7
1 2 1 5 4 4 1

样例输出 #1

1
5

提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

  1. 1：查找单词 1 并调入内存。
  2. 1 2：查找单词 2 并调入内存。
  3. 1 2：在内存中找到单词 1。
  4. 1 2 5：查找单词 5 并调入内存。
  5. 2 5 4：查找单词 4 并调入内存替代单词 1。
  6. 2 5 4：在内存中找到单词 4。
  7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 55 次词典。

数据范围

  • 对于 10%10\% 的数据有 M=1M=1，N≤5N \leq 5；
  • 对于 100%100\% 的数据有 1≤M≤1001 \leq M \leq 100，1≤N≤10001 \leq N \leq 1000。

解析

队列

首先先向不太了解的同学们简单科普一下队列这个东西：

队列是一种特殊的线性表（你也可以理解为数组），它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

怎么简单地理解它呢？你可以想想你平时吃饭排队时，是不是需要从后面排，然后到了第一个的时候就打饭离开呢？没错，队列也是这样的，我们从后面插入元素，直到前面的元素都被拿走后，就到了队头（front），此时该元素就能被删除了。而从后面插入的地方就叫做队尾（rear）。

队列的实现

在C++中有两种实现队列的方式：手搓和上STL。手搓队列就是使用数组模拟，用一个变量记录队头索引，一个记录队尾索引，然后根据索引插入、删除、查询即可。但是这种方法会导致空间的浪费，并且稍微麻烦（但是有时候有优点），所以我推荐使用stl。

使用stl时，我们使用这种语法创建：

1
queue<type> q;

type部分填入的是类型，代表队列可存储的数据类型：比如int、double、char等。

假如存储int的话，可以这样创建：

1
queue<int> q;

哦，对了，要开启STLQueue的大门，我们还需要引入 米奇妙妙屋 头文件：

1
#include <queue>

如果你使用了万能头，即#include <bits/stdc++.h>，就不用引入了。

队列的基础操作也很简单：

1
2
3
4
5
6
7
//这里只介绍基本语法
q.front(); //获取队头
q.rear(); //获取队尾
q.push(n); //在队尾插入元素,即入队,插入类型取决于您声明时的类型
q.pop(); //移除队头元素,即出队
q.size(); //获取队列长度
q.empty(); //获取队列是否为空,效果等同于q.size()==0

解析

这道题就是一个简单的模拟题简单来说就是如果内存里面没有这个单词（其实是一个数）的话就从外存入队，如果内存容量不够，出队即可。

哦，对了，每次查询时还要计数噢！

代码

话不多说上代码

我已经认真读完并理解了上面的解析，并且不会直接照搬
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
bool find(queue<int> q, int n){ //从内存里查找
    int size = q.size();
    for (int i=0;i<size;i++){
        int a = q.front();
        if (a == n){ //不断出队,如果发现元素返回
            return true;
        }
        q.pop();
    }
    return false; //没有元素,需要查询
}
int main(){
    ios::sync_with_stdio(false); //读入优化,虽然没用(
    int m,n,c=0;
    queue<int> q; //初始化
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int t; 
        cin>>t;
        if(!find(q,t)){ //从外存调入
            if(q.size()<m){
                q.push(t); //容量足够
                c++;
            }
            else{
                q.pop(); //容量不足,先出队再入队
                q.push(t);
                c++;
            }
        }
    }
    cout<<c; 
    return 0;
}