题解 | #[NOIP2010]机器翻译#

枚举

可以用队列（先进先出）结构来解决

这里给出一种仅用数组的方法

开两个大数组a和flag

其中a用来按顺序存储载入内存的数据（包括历史数据），同时设置一个游标fm指向下一个空位置，设置另一个游标cl_f指向当前内存的首位数据（有点类似静态链表的游标）；flag用来存储相应数据的状态，0为不在内存中，1为在内存中；

此时fm-1的值即为访问外存的次数（因为fm指向的是当前内存最后一个数据的下一个位置）

#include <iostream>
using namespace std;
#define N 1010

int main(){
    int m,n,fm = 1,temp_m = 0,cl_f = 1;    //temp_m为当前内存数据总数
    int a[N],flag[N];
    cin>>m>>n;
    
    for(int j = 0;j < N;j++)    //初始化标志数组
        flag[j] = 0;
    
    for(int i = 0;i < n;i++){
        int temp_in;
        cin>>temp_in;
        
        if(flag[temp_in] == 0){
            if(temp_m == m){    //
                flag[a[cl_f++]] = 0;    //如果内存已满，最先进入的数据相应标志位置0
                flag[temp_in] = 1;      //最新数据对应的标志位置1
                a[fm++] = temp_in;      //同时把最新的数据载入内存
            }
            else{
                flag[temp_in] = 1;
                a[fm++] = temp_in;
                temp_m++;
            }
        }
    }
    cout<<fm-1;
    return 0;
}