P1540 机器翻译——题解

思路

用队列保存当前内存中的单词，队首就是最早进入内存、需要最先淘汰的单词；再用布尔数组 in[x] 表示单词 x 是否在内存中。

依次处理每个单词 x：

• 若 in[x] 为真，不做任何操作；
• 否则查词典次数加一：
  • 若内存已经有 $M$ 个单词，弹出队首，并把被弹出单词的 in 标记清除；
  • 将 x 加入队尾，并把 in[x] 设为真。

复杂度

时间复杂度 $O(N)$，空间复杂度 $O(M+1001)$。

参考代码

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

int q[1005];
bool inMemory[1001];

int main() {
    int M, N;
    cin >> M >> N;
    int head = 0, tail = 0, ans = 0;

    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        if (inMemory[x]) continue;

        ans++;
        if (tail - head == M) {
            inMemory[q[head]] = false;
            head++;
        }
        q[tail++] = x;
        inMemory[x] = true;
    }

    cout << ans << '\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int q[1005]; bool inMemory[1001]; int main(){ int M,N; cin>>M>>N; int head=0,tail=0,ans=0; for(int i=1;i<=N;i++){ int x; cin>>x; if(inMemory[x]) continue; ans++; if(tail-head==M){ inMemory[q[head]]=false; head++; } q[tail++]=x; inMemory[x]=true; } cout<<ans<<'\n'; return 0; }