欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P2776 [SDOI2007]小组队列

程序员文章站 2024-03-19 11:55:10
...

P2776 [SDOI2007]小组队列

题目背景
嘛,这道非常简单的给大家提供信心的省选题洛谷居然没有!

这么简单的题怎么可以没有!

给大家提升士气是义不容辞的责任!

所以我就来补一下啦..

值得一提的是,标程是我自己做的..

很渣,因为数据很水所以能AC..

大神勿喷..

题目描述
有 m 个小组, n 个元素,每个元素属于且仅属于一个小组。

支持以下操作:

push x:使元素 x 进队,如果前边有 x 所属小组的元素,x 会排到自己小组最后一个元素的下一个位置,否则 x 排到整个队列最后的位置。

pop:出队,弹出队头并输出出队元素,出队的方式和普通队列相同,即排在前边的元素先出队。

输入输出格式
输入格式:
第一行有两个正整数 n, m,分别表示元素个数和小组个数,元素和小组均从 0 开始编号。

接下来一行 n 个非负整数 Ai,表示元素 i 所在的小组。

接下来一行一个正整数 T ,表示操作数。

接下来 T 行,每行为一个操作。

输出格式:
对于每个出队操作输出一行,为出队的元素。


首先, 若是在队列中有某一组元素, 那么他们的序号的连续的, 弹出满足先进先出这一性质; 同时, 我们把一整组看做一个元素, 这些元素满足先进先出
所以我们开两类队列, 第一类总队列: 记录组的队列, 第二类记录每一个组内的元素的队列。

当某一元素加入时, 若这一组之前没有出现(体现在次组队列大小为 \(0\)), 我们就在总队列中将次组元素入队; 同理, 当弹出后次组元素个数为 \(0\) 我们就弹出总队列首即可

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 100019;
queue<int>Q;
queue<int>q[319];
int num, na;
int father[maxn];
int main(){
    num = RD();RD();
    for(int i = 0;i < num;i++)father[i] = RD();
    na = RD();
    char cmd[19];
    for(int i = 1;i <= na;i++){
        cin>>cmd;
        if(cmd[1] == 'u'){
            int x = RD();
            if(q[father[x]].empty())Q.push(father[x]);
            q[father[x]].push(x);
            }
        else{
            int u = Q.front();
            printf("%d\n", q[u].front());
            q[u].pop();
            if(q[u].empty())Q.pop();
            }
        }
    return 0;
    }