CF1234B2题解

FiraCode · 2022-05-11 19:42:38 · 题解

题解思路：

用 deque 来维护序列，然后，用一个 map 来看是否添加过了。

具体分为一下步骤：

若当前已经有了，那么直接 continue。

若长度 = k 了，就弹出队尾，然后把标记删掉。

然后插入队头,然后再标记一下就可以了。

AC CODE:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <deque>
#include <map>
using namespace std;
int n , k;
int a[200010];
deque <int> q;//维护序列
map <int , int> ma;//在聊天框里是否出现过
int main(){
    scanf ("%d%d" , &n , &k);
    for (int i = 1; i <= n; ++ i)
        scanf ("%d" , &a[i]);
    for (int i = 1; i <= n; ++ i) {
        if (ma[a[i]]) continue;//已经出现过了，那么就跳过
        if (q.size () == k) ma[q.back()] = false , q.pop_back();//弹出，然后去掉标记
        if (!ma[a[i]])q.push_front (a[i]) , ma[a[i]] = true;//插入，标记
    }
    cout << q.size() << endl;//输出长度
    for (int i = 0; i < q.size(); ++ i)
        cout << q[i] << ' ';//输出聊天窗里的数
    return 0;//完结散花
}

码字不易，求赞！