P1540 机器翻译

用队列维护单词进入内存的时间顺序，并根据题目所给的内存限制动态调整内存区域存储的单词，并对内存中包括的单词做标记
注意：题面说如果内存中已经存在这个单词就不要到外存去找了，相应的不需要把这个单词放到内存里。
复杂度：\(O(n)\)

#include<iostream>

using namespace std;

const int N = 1010;

int st[N];
int m, n;
int q[N], hh, tt = -1;

int main(){
    cin >> m >> n;
    
    int res = 0;
    while(n --){
        int x;
        
        cin >> x;
        
        if(st[x]) continue;
        res ++;
        while(tt - hh + 1 > m - 1) st[q[hh ++]] --;
        st[x] ++;
        q[++ tt] = x;
    }
    
    cout << res;
    
    return 0;
}

P1540 机器翻译

原文：https://www.cnblogs.com/tomori/p/13854160.html