solution

传送门

思路

我们可以用队列 $q$（即内存）加数组 $flag$ 来模拟一下。
首先，读入每一个单词 $x$。
然后，判断如果 flag[x]=1 代表 $x$ 在内存里，直接跳过；如果 flag[x]=0 代表 $x$ 不在内存里，需要查词典，把 $x$ 压入队列，答案加 $1$。
最后，特判一下，如果 q.size()>m 先把 flag[q.front()] 记为 $0$，再把 q.front() 弹出。

std：

#include<bits/stdc++.h>
using namespace std;
int m,n,x,ans,flag[1010];
queue<int>q;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
    	cin>>x;
    	if(flag[x]==1){
    		continue;
		}
		else{
			ans++;
			q.push(x);
			flag[x]=1;
			if(q.size()>m){
				flag[q.front()]=0;
				q.pop();
			}
		}
	}
	cout<<ans;
	return 0;
}

题目描述

有一个内存容量为M的词典缓存，每次查询一个单词。如果该单词已在缓存中，则直接命中；如果不在，则需要将该单词调入缓存。若缓存已满，则需置换出某个单词。请计算在整个查询过程中，共发生了多少次缺页（即需要调入缓存的次数）。

输入格式

第一行包含两个整数M和N（0 < M ≤ 100，0 < N ≤ 1000），分别表示内存容量和查询次数。
第二行包含N个整数，按查询顺序排列的单词序列。

输出格式

一个整数，表示缺页次数。

样例输入

2 7
1 2 1 5 4 4 1

样例输出

5

算法思路

本题采用FIFO（先进先出）页面置换算法。核心思想是：当需要置换页面时，选择最早进入内存的页面进行置换。具体步骤如下：

1. 初始化一个空队列（记录内存中单词的进入顺序）和一个集合（快速判断单词是否在内存中）。
2. 遍历每个查询单词：
   • 若单词在内存中，直接命中，不增加缺页次数。
   • 若单词不在内存中，缺页次数加1，将单词加入内存（队列和集合）。
   • 若内存满（队列大小等于M），置换出队列队首（最早进入的单词），再加入新单词。
3. 遍历结束后，输出缺页次数。

代码实现

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;
    queue<int> memory;  // 记录内存中单词的进入顺序
    unordered_set<int> in_memory;  // 快速判断单词是否在内存中
    int page_fault = 0;  // 缺页次数

    for (int i = 0; i < N; ++i) {
        int word;
        cin >> word;

        // 单词在内存中，直接命中
        if (in_memory.find(word) != in_memory.end()) {
            continue;
        }

        // 单词不在内存中，缺页次数加1
        page_fault++;
        in_memory.insert(word);
        memory.push(word);

        // 若内存满，置换最早进入的单词
        if (memory.size() > M) {
            int oldest = memory.front();
            memory.pop();
            in_memory.erase(oldest);
        }
    }

    cout << page_fault << endl;
    return 0;
}

样例解释

以样例输入M=2（内存容量2）、N=7（查询序列[1,2,1,5,4,4,1]）为例：

• 1：不在内存，缺页1，内存[1]
• 2：不在内存，缺页2，内存[1,2]
• 1：在内存，不缺页
• 5：不在内存，缺页3，内存满，置换1，内存[2,5]
• 4：不在内存，缺页4，内存满，置换2，内存[5,4]
• 4：在内存，不缺页
• 1：不在内存，缺页5，内存满，置换5，内存[4,1]
  共缺页5次，与样例输出一致。