洛谷题单指南-线性表-P1540 [NOIP2010 提高组] 机器翻译

原题链接：https://www.luogu.com.cn/problem/P1540

题意解读：本题模拟内存的调入调出，内存先入先出的特性就是队列。

解题思路：

本题需要两种数据结构：队列、数组

队列用来模拟内存的操作，数组充当hash表用于判断单词在内存是否存在

核心逻辑：对于每一个单词，如果内存不存在，查一次词典，再将单词存入内存，如果内存满要先清除最早进入的单词。

100分代码：

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

queue<int> q;
int flag[1005];
int ans;

int main()
{
    int m, n, x;
    cin >> m >> n;
    while(n--)
    {
        cin >> x;
        if(!flag[x]) //如果x不在内存
        {
            ans++; //查词典
            if(q.size() >= m) //如果队列已满，清除最早进入的单词
            {
                flag[q.front()] = false;
                q.pop();
            } 
            q.push(x);
            flag[x] = true;
        }
    }
    cout << ans;

    return 0;
}