NC16589 机器翻译

#include<iostream>
using namespace std;
int main()
{
    int m, n;//m是内存大小，n是文章词数
    int cnt = 0;//cnt是查询词典的次数
    cin >> m>>n;
    int* memory = new int[m];
    int* vis = new int[n];//vis记录在内存中是否出现过
    int x;
    int replace = 0;
    for (int i = 0; i < n; i++)
    {
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        if (vis[x] == 0)
        {
                if(cnt>=m)
                {
                    vis[memory[replace % m]] = 0;
                }
                memory[replace%m] = x;
                vis[x] = 1;
                replace++;
                cnt++;
        }
    }
    cout << cnt;
}

本题需要确定几个情况： 1.最初内存没满的时候不需要进行替换，只进行赋值（当然上述代码中memory[replace%m] = x;这句能达到同样效果） 2.内存有相同值直接进入下一次循环 3.内存无相同值且内存已满时需要替换掉最先读入内存的数（该数在memory中的位置由变量replace%m记录）,此时需要将vis数组中被替换的数对应的值改为0，替换进的新数的vis改为1 4.在替换时vis[memory[replace % m]] = 0;这行代码是通过memory[replace % m]找到被替换的值的，所以这行代码一定要放在memory[replace%m] = x;之前