B2. Social Network (hard version)

Codeforces Round #590 (Div. 3)

题目链接:https://codeforces.com/contest/1234/problem/B2

题目描述:

题目

思路:

就没什么好说的,千万不要想当然!一个消息的总数n,一个最多可以显示几条消息的数目k(只显示k条最新的消息,其实是发送消息的id号,如果同一个id发送多条消息,算作一个显示),n条发送消息的id号。考虑id一般都是很长的,所以map标记这个id是否当前显示中,如果新消息的发送id不在当前显示的范围且,已经显示了k个id,那么将最早收到的id删掉(并且删除map里面关于这个id的值),加入新的id(先进先出的特点,自然联想到队列)。最终的信息数目就是队列中元素的个数,展示的id就是队列里面的id。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<map>
using namespace std;
const int maxn=2e5+5;
int a[maxn];
map<int,int>mp;
queue<int>mas;
int ans[maxn];
int main(){
    int n,k;
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d%d",&n,&k);
    int len;
    len=0;
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(len<=k&&mp[a[i]]==0){
            mp[a[i]]=1;
            if(len==k){
                int tt;
                tt=mas.front();
                mp[tt]=0;
                mas.pop();
            }
            mas.push(a[i]);
            len=mas.size();
        }
    }
    printf("%d\n",len);
    int j=1;
    while(!mas.empty()){
        ans[j++]=mas.front();
        mas.pop();
    }
    for(int i=len;i>0;i--){
        printf("%d ",ans[i]);
    }
 
    return 0;
}
Last modification:December 15th, 2019 at 12:20 am
如果觉得我的文章对你有用,请随意赞赏