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

[NOIP2010]机器翻译

https://ac.nowcoder.com/acm/problem/16589

枚举

可以用队列(先进先出)结构来解决

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

开两个大数组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;
}
全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务