记录154

#include<bits/stdc++.h>
using namespace std;

queue<int>q; // 使用队列维护内存中的单词(FIFO)
bool vis[1001]; // 标记数组，记录单词是否在内存中(0表示不在)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m,n;
    cin>>m>>n; // 输入内存容量和文章长度
    
    int ans=0; // 记录查词典的次数
    for(int i=1;i<=n;i++){ // 处理每个单词
        int x;
        cin>>x; // 读取当前单词
        
        if(!vis[x]){ // 如果单词不在内存中
            ans++; // 需要查词典
            vis[x]=true; // 标记为在内存中
            q.push(x); // 加入队列
            
            if(q.size()>m){ // 如果内存已满(超过M个单词)
                int top=q.front(); 
                q.pop(); // 移除最早进入的单词(队首)
                vis[top]=false; // 更新标记，表示该单词已被踢出内存
            }
        }
    }
    
    cout<<ans; // 输出总查词典次数
    return 0;
}

题目传送门https://www.luogu.com.cn/problem/P1540

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

 核心解题思路

这道题是一道非常经典的数据结构模拟（队列 + 哈希标记）问题，完美体现了计算机操作系统中“缓存淘汰机制”的雏形。

1. 问题转化与数据结构选择：
   题目中内存的存取规则是：“若内存已满，清空最早进入内存的那个单词”。这种“先进先出”（FIFO, First In First Out）的特性，天然对应了数据结构中的队列（Queue）。我们可以用一个队列来维护当前内存中单词的先后顺序。

2. 算法设计（队列模拟 + 布尔数组标记）：
   由于单词的数值大小不超过 1000，我们可以使用一个大小为 1001 的布尔数组 vis 作为哈希表（或称为标记数组），用来记录某个单词当前是否在内存中。
   遍历文章中的每个单词时：

   • 如果 vis[x] 为真，说明单词在内存中，直接跳过。
   • 如果 vis[x] 为假，说明内存中没有，需要查词典（答案 ans++）。随后将该单词压入队列，并将 vis[x] 设为真。
   • 关键淘汰机制：每次新单词入队后，检查队列大小是否超过了内存容量 M。如果超过了，说明内存满了，必须将队首（最早进入的）单词弹出，并将其在 vis 数组中的标记清除。

 代码分块详细解释

1. 头文件与全局数据结构定义

#include<bits/stdc++.h>
using namespace std;
queue<int> q; // 使用队列维护内存中的单词(FIFO)
bool vis[1001]; // 标记数组，记录单词是否在内存中(0表示不在)

• 详细分析：queue<int> 是 C++ STL 提供的队列容器，支持 push（入队）、pop（出队）、front（获取队首）等操作，完美契合题目要求。bool vis[1001] 作为一个全局数组，默认会被初始化为 false，这恰好对应了“翻译开始前，内存中没有任何单词”的初始状态。

2. 主函数与变量初始化

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m, n;
    cin >> m >> n; // 输入内存容量和文章长度
    
    int ans = 0; // 记录查词典的次数

• 详细分析：m 代表内存容量，n 代表文章长度。ans 初始化为 0，用于累计最终需要去外存查找词典的次数。

3. 核心逻辑：遍历单词与内存状态维护

    for(int i = 1; i <= n; i++){ // 处理每个单词
        int x;
        cin >> x; // 读取当前单词
        
        if(!vis[x]){ // 如果单词不在内存中
            ans++; // 需要查词典
            vis[x] = true; // 标记为在内存中
            q.push(x); // 加入队列
            
            if(q.size() > m){ // 如果内存已满(超过M个单词)
                int top = q.front(); 
                q.pop(); // 移除最早进入的单词(队首)
                vis[top] = false; // 更新标记，表示该单词已被踢出内存
            }
        }
    }

• 详细分析：这是代码的灵魂所在，完美模拟了翻译软件的缓存逻辑。
  • 内存命中判断：if(!vis[x]) 是程序的入口。如果 vis[x] 已经是 true，说明这个单词还在内存里，无需任何操作，直接处理下一个单词。
  • 查词典与入队：如果不在内存中，ans 加 1，并将该单词的状态标记为 true，同时通过 q.push(x) 将其放入队列尾部。
  • 内存淘汰机制：新单词入队后，队列的长度可能变为 M+1。此时必须执行 q.pop() 将队首元素（最早进入内存的单词）踢出。特别注意：在弹出队首元素 top 后，必须同步执行 vis[top] = false。如果不取消标记，当这个被踢出的单词在文章后面再次出现时，程序会错误地认为它还在内存中，从而导致答案错误。

4. 输出结果

    cout << ans; // 输出总查词典次数
    return 0;
}

• 详细分析：循环结束后，ans 中存储的就是整个翻译过程中，因为内存缺失而去外存查找词典的总次数。

核心逻辑总结表