题解 | #[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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:23
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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