P1540 Solution

题目传送门

用 vis 数组标记每个数在内存中的状态，再用队列模拟内存。每次输入一个数，如果它不在内存中，那么就把它打上标记，并加入队列。如果此时队列长度 >m，那么就把第一个元素换一下标记并从队列中移除。统计次数输出即可。

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

const int N = 1005;

bool vis[N];
queue<int> q;

int main()
{
    int n, m;
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        if (!vis[x])
        {
            ans++;
            q.push(x);
            vis[x] = true;
        }
        if (q.size() > n)
        {
            vis[q.front()] = false;
            q.pop();
        }
    }
    cout << ans;
    return 0;
}