题解 P1540 【机器翻译】

0104154308_f · 2019-08-15 15:52:52 · 题解

看到前面各位dalao没有使用queue的我在此献上我的蒟蒻代码

模拟内存

queue：新的元素在队列最后入队每次将第一个元素出队\ 很明显这就是一个队列先进的先出当队列长度等于m时删除第一个元素再加入新的元素。

标记是否已在内存中

这时只需要一个flag数组当这个元素入队时flag[t]=1；（flag初始化为0）\ 每当flag.size()等于m时flag[l.front]=0从内存中删掉这个元素

不多bb上代码

#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
queue<int>l;
bool flag[10001]={};
int m,n,t,ans=0;
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        if(!flag[t])
        {
            //printf("%d\n",t);
            ans++;
            if(l.size()==m)
            {   
                flag[l.front()]=0;
                l.pop();
                l.push(t);
                flag[t]=1;
            }
            else
            {
                l.push(t);
                flag[t]=1;
            }
        }
    }
    printf("%d",ans);
    return 0;
}