原题目链接:
P1540 [NOIP2010 提高组] 机器翻译 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原题目截图:
思路分析:
读懂题意,直接模拟过程即可。这是一道很简单的题目。
思路过程很类似 模拟页面置换算法中的 先进先出(FIFO)策略。
因此我们很容易想到,要用队列来实现。
下面是具体步骤:
- 遍历文章中的每一个单词。
- 对于每个单词,检查它是否已经在内存中(即在
memory_set
集合中):- 如果页面不在内存中(
memory_set.count(word) == 0
),则需要访问外存,然后将其加载到内存:- 增加访问外存的次数
count
。 - 检查内存中的 word 数量是否已经达到上限
m
:- 如果是,从队列(内存)中移除最早进入的单词(
que.front()
),并从memory_set
中删除该单词。
- 如果是,从队列(内存)中移除最早进入的单词(
- 将当前单词加入队列(模拟加载到内存)。
- 将当前单词加入
memory_set
集合(模拟内存中的单词)。
- 增加访问外存的次数
- 如果页面不在内存中(
- 遍历结束后,输出访问外存的次数
count
。
解决代码:
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<queue>
int main() {
int m, n;
cin >> m >> n;
vector<int>article(n);
queue<int>que;
for (int i = 0; i < n; i++) {
int word;
cin >> word;
article[i] = word;
}
set<int>memory_set;
int count = 0;//访问外存次数
for (int word : article) {
if (memory_set.count(word) == 0) {
count++;
if (que.size() >= m) {
int first = que.front();
que.pop();
memory_set.erase(first);
//从内存抹去最早进入的
}
que.push(word);
memory_set.insert(word);
}
}
cout << count;
return 0;
}
今天的题目比较简单,愿诸君共勉之。
标签:count,set,word,NOIP2010,int,机器翻译,内存,memory,洛谷 From: https://blog.csdn.net/weixin_70448721/article/details/142547217