NOIP2010机器翻译

链接：https://ac.nowcoder.com/acm/problem/16589
来源：牛客网

这个题目印象很深，其实在写牛客学习题单的时候接触过这道题，当时是在队列应用的时候练习了这一道题。
但是在听雨巨讲解这道题的时候我直接懵逼了。
因为我没有想到数列的用法可以这样使用，估计也是刚开始的原因听不太懂，最后还是问豆包一步一步看懂代码

这个题目的题意还是很好理解的，要注意的点主要是要分情况：是否命中的问题以及是否缓存已满的问题，需要解题人可以清楚的找到临界点。难点就是当缓存满的时候如何找到那个需要被删除的单元。
雨巨的解法一：
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int m,n;
int vis[1010];
int main(){
    cin>>m>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(vis[x]!=0)continue;
        cnt++;
        if(m>0){
            vis[x]=i;
            m--;
        }
        else{
            int minn=i,pos=0;
            for(int j=0;j<=1000;j++){
                if(vis[j]!=0&&vis[j]<minn) 
                minn=vis[j],pos=j;
            }
            vis[pos]=0;
            vis[x]=i;
        }
        
    }
    cout<<cnt;
}
第一个解法是很暴力的就是用一个vis数组来记录当前元素进入内存的时间，如果没有进入则置为0，这个数组的意义是我第一次见到，所以当时的理解真的不行，根本不会用。然后命中了直接continue掉，没命中用cnt直接记录次数。这个时候要开始考虑缓存空间是否满了，没有满的话就直接就继续vis统计时间，并且逐渐减少缓存的剩余空间；如果满了的话就要遍历整个n（避免缺漏），遍历的时候找到那个最早进入缓存空间的元素（内存for循环的逻辑），找到以后踢出去最早位置的数，并把当前位置元素时间插入。

这个当时是内层for循环逻辑没有看懂，是因为时间戳是随机的不是有序的，这个要注意。
当然这个解法需要维护整个内存空间，时间复杂度为O（n*1000）

第二个解法：不难看出，如果没有在缓存空间里的部分可以不用关注，只需要关注目前在缓存空间里面的内容，所以可以用一个数组来表示当前缓存里面数据，用一个数组来表示数据是否在缓存中代码如下：
#include<bits/stdc++.h>
using namespace std;
int m,n,x;
int a[1005];
int vis[1005];
int cnt=0;
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(vis[x]==1)continue;
        a[cnt++]=x;
        vis[x]=1;
        if(cnt>m) vis[a[cnt-m-1]]=0;
    }
    cout<<cnt;
}
这样我们发现，只需要用a数组维护缓存空间即可，空间复杂度降到O（n）
经过这一道题发现优化问题的时候只关心对结果有影响的地方可以大大简化问题。这个思想在后面的问题里面也会有所体现。