洛谷每日一题（P1540 [NOIP2010 提高组] 机器翻译）

原题目链接：

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;
	

}

今天的题目比较简单，愿诸君共勉之。