A85786 题解

$\text{\huge 机器翻译}$

$\text{\large 题目传送门}$

本题主要考察队列。因为在机器翻译软件中，内存的替换是符合“先进先出”逻辑的，所以可以考虑用数组模拟队列实现，主要实现步骤如下：

• 用数组a[1005]模拟内存。
• 用变量top表示内存中最后一个单词的位置。
• 因为top为最后一个单词的位置，并且内存中有m个单元，所以max(1,top-m+1)就是内存中第一个单词的位置。
• 循环输入当前单词t。
  • 如果内存中包含t，不更新内存。
  • 否则更新内存，使a[++top]=t。

$\text{\large AC~Code}$：

#include<bits/stdc++.h>
using namespace std;
int m,n,a[1005],t,top,cnt;
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>t;
        bool flag=0; //flag表示内存中是否包含单词t
        for(int j=max(1,top-m+1);j<=top;j++)
            if(a[j]==t){
                flag=1;
                break;
            }
        if(flag==1) continue; //如果t在内存中，跳过循环
        else a[++top]=t,cnt++; //如果t不在内存中，更新内存
    }
    cout<<cnt;
}

$\text{\large 时间复杂度：}\mathcal{O(n \times m)}$