BNUOJ 52511 Keep In Line

你的名字 2021-03-28 13:53 575阅读 0赞

队列，$map$。

每次出队进行出队操作的是时候，先把队列中需要出队的人全部出队，然后比较对头和当前出队的人是否相同。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int T,n,sz,sum;
  4. int f[100010];
  5. char op[100];
  6. int main()
  7. {
  8.     scanf("%d",&T);
  9.     while(T--)
  10.     {
  11.         scanf("%d",&n); sum=sz=0;
  12.         map<string,int>zhuan;
  13.         queue<int>Q;
  14.         memset(f,0,sizeof f);
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             scanf("%s",op);
  18.             if(op[0]=='i')
  19.             {
  20.                 scanf("%s",op);
  21.                 zhuan[op]=++sz;
  22.                 Q.push(sz);
  23.             }
  24.             else
  25.             {
  26.                 while(1)
  27.                 {
  28.                     if(Q.empty()) break;
  29.                     if(f[Q.front()]==0) break;
  30.                     Q.pop();
  31.                 }
  32.                 scanf("%s",op);
  33.                 int id = zhuan[op];
  34.                 f[id]=1;
  35.                 if(Q.front()!=id) sum++;
  36.             }
  37.         }
  38.         printf("%d\n",n/2-sum);
  39.     }
  40.     return 0;
  41. }

发表评论

表情：
评论列表 （有 0 条评论，575人围观）

还没有评论，来说两句吧...

相关阅读

    相关 BNUOJ 52511 Keep In Line

    队列，$map$。 每次出队进行出队操作的是时候，先把队列中需要出队的人全部出队，然后比较对头和当前出队的人是否相同。 #include<bits/stdc++.h>...

    你的名字你的名字/ 0 赞/ 576 阅读