CodeForces 705C Thor

队列的应用

题目链接CodeForces 705C

题目大意

一个手机，上面有n个应用。有m个操作。a b为一个操作。a=1,b应用产生一个消息;a=2,读取b应用的所有消息;a=3,读取前b条消息。注意消息可以重复读取。输出每一次操作后未读取的消息数目。

用队列模拟过程即可，但注意消息可重复读取，注意细节处理。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int num[300010];//队列中的某应用产生消息的总数量
int used[300010];//队列中某应用已读的消息数量 是否读取过
int main()
{
        int n,m,ans=0,sum=0;
        cin>>n>>m;
        queue<int> q;
        memset(num,0,sizeof(num));
        memset(used,0,sizeof(used));
        while(m--)
        {
                int a,b;
                cin>>a>>b;
                if(a==1)
                {
                       q.push(b);
                       num[b]++;//消息+1
                       ans++;
                }
                else if(a==2)//读取b应用所有消息--消息仍在队列中
                {
                        if(num[b]>used[b])//队列中存在未读消息
                        {
                                sum+=(num[b]-used[b]);//队列中已读取的消息数目和
                        }
                        used[b]=num[b];
                }
                else if(a==3)
                {
                        if(ans-q.size()<b)//已经读取并弹出的消息<要读取的消息数
                        {
                                int k=0;
                                b-=(ans-q.size());//真正要读取的数目=要读取总数目-减去重复读取的数目
                                while(!q.empty()&&k<b)
                                {
                                        int x=q.front();
                                        q.pop();
                                        if(used[x]>0)//如果弹出了读取过的消息
                                        {
                                                sum--;
                                                used[x]--;
                                        }
                                        num[x]--;
                                        k++;
                                }
                        }
                }
                printf("%d\n",q.size()-sum);
        }
        return 0;
}