首页 > 试题广场 >

机器翻译

[编程题]机器翻译
  • 热度指数：2785 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}牛牛的电脑上安装了一个机器翻译软件，它依次将每个英文单词替换为对应的中文含义。软件内部有 M 个缓存单元，每个单元存放一个单词和译义。翻译某个单词时：
\hspace{23pt}\bullet\,如果缓存中已有该单词，则直接使用（缓存命中）；
\hspace{23pt}\bullet\,否则需要到外存词典查找（缓存未命中），并将该单词及译义插入缓存：若缓存未满，则占用一个空闲单元；若缓存已满，则清除最早进入缓存的单词后插入新单词。
\hspace{15pt}给定长度为 N 的文章（由 N 个整数编码表示单词），初始缓存为空，统计翻译过程中需要查词典的次数。

输入描述:
\hspace{15pt}第一行输入两个整数 M,N（1 \leqq M \leqq 100，1 \leqq N \leqq 1000），分别表示缓存容量和文章单词数。
\hspace{15pt}第二行输入 N 个整数 w_1,w_2,\dots,w_N（0 \leqq w_i \leqq 1000），表示文章中按顺序出现的单词编码。


输出描述:
\hspace{15pt}输出一个整数，表示翻译过程中缓存未命中（查词典）的总次数。
示例1

输入

3 7
1 2 1 5 4 4 1

输出

5

说明

翻译过程示例（缓存状态记录自左向右为最早到最近）：
初始：空
1: miss，缓存->[1]
2: miss，缓存->[1,2]
1: hit，缓存->[1,2]
5: miss，缓存->[1,2,5]
4: miss，缓存->[2,5,4]（替换1）
4: hit，缓存->[2,5,4]
1: miss，缓存->[5,4,1]（替换2）
共 miss 5 次。

备注:

算法知识视频讲解
添加回答
Java
拒绝无效加班的柯基很想被叫靓仔头像 拒绝无效加班的柯基很想被叫靓仔
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int m = in.nextInt();
            int n = in.nextInt();
            int[] list = new int[n];
            for(int i = 0;i < n;i++){
                list[i] = in.nextInt();
            }
            Queue<Integer> huancun = new LinkedList<>();
            ArrayList<Integer> arr = new ArrayList<>();
            int count = 0;
            for(int i = 0;i < n;i++){
                Boolean find = false;
                if(huancun.isEmpty()){
                    count++;
                    huancun.add(list[i]);
                    arr.add(list[i]);
                }else{
                    if(arr.size() > m){
                        for(int j = arr.size() - m;j < arr.size();j++){
                            if(arr.get(j) == list[i]){
                                find = true;
                            }
                        }
                    }else{
                        for(int j = 0;j < arr.size();j++){
                            if(arr.get(j) == list[i]){
                                find = true;
                            }
                        }
                    }
                    if(find == true){
                        continue;
                    }else{
                        if(arr.size() < m){
                            count++;
                            huancun.add(list[i]);
                            arr.add(list[i]);
                        }else{
                            huancun.poll();
                            count++;
                            huancun.add(list[i]);
                            arr.add(list[i]);
                        }
                       
                    }
                }
            }
            System.out.println(count);
        }
    }
}
发表于 2025-07-16 15:44:24 回复(0)
提交观点

问题信息

NOIP复赛 枚举
难度：
1条回答 888浏览

热门推荐

通过挑战的用户

查看代码

相关试题

机器翻译

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号