题解 P1540 【机器翻译】

· · 题解

可以看成一个队列的问题

检测队列中是否存在，可以使用一个p数组，长度为1001 因为题目要求0≤N≤1000 默认p数组每一个都为0，只要p[N]==0

就队列不存在这个元素，相当于一个map一一对应 N相当于p的下标 只要检测N作为下标所对应的数是否为0就可以检测是否存在

添加后p[N]++ 这时再有同样元素，就可以知道其不为0,所以不用翻字典

当队列达到满的时候，队头出来，队尾添加元素 这时候队头元素作为下标对应的p就应该--置0 并同时把p[队尾元素]++

同时设置一个检测队列是否满的值和翻字典的次数的值即可

Java

import java.util.*; public class Main {

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();
    int a[] = new int[m];
    for (int i = 0; i < m; i++) {
        a[i] = sc.nextInt();
    }

    int p[] = new int[1001];
    Queue<Integer> my = new LinkedList<Integer>();
    int index = 0;//队列长度
    int count = 0;

    for (int i = 0; i < m; i++) {
        if (p[a[i]] == 0) {
            if(index<n) {
                p[a[i]]+=1;
                my.add(a[i]);
                index++;
                count++;
            }
            else {
                p[my.poll()]-=1;
                my.add(a[i]);
                p[a[i]]+=1;
                count++;

            }

        } 
    }
    System.out.println(count);

}

}