题解 P2776 【[SDOI2007]小组队列】

无解双八卦 · 2017-12-08 11:42:54 · 题解

写这篇题解两个原因，一个是挂了好几次难受（打错一个字母），

一个是看到看到各种高端操作，蒻苟实在学不来，搞了静态链表。

首先这道题我一看往队列中插元素这不是链表？然后再一看数据范围好了开始写。

直接上代码+注释：

#include<cstdio>
using namespace std;
int m[100000],lb[100000][2]={0},head[300]={0};//m记录小组，lb0记录数字，1记录后继指针，
//head记录链表中小组最后一个元素的位置，如果队列中没有小组元素就记0.（建议记-1）
int main()
{
    int n,k,t,l=1,r=1,t3=0;char c[5];//k是各处乱用的变量，l是该输出的位置，r是该输入的位置，t3是指向r的位置，也就是链表的最后一位
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    scanf("%d",m+i);
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%s",c);
        if(c[1]=='u')//push
        {
            scanf("%d",&k);
            lb[r][0]=k;//入队
            if(!head[m[k]])//队列中没有该小组元素
            {
                t3=r;lb[t3][1]=++r;//最后一位元素就是新加进来的
            }
            else//队列中有该小组元素
            {
                lb[t3][1]++;lb[r][1]=lb[head[m[k]]][1];//不管该小组是不是最后一个小组，都可以保证新的元素指向该指的位置
                if(t3==head[m[k]])t3=r;//如果是最后一个小组就改变最后一个元素的位置
                lb[head[m[k]]][1]=r++;
            }
            head[m[k]]=r-1;
        }
        else//pop
        {
            printf("%d\n",lb[l][0]);
            if(head[m[lb[l][0]]]==l)
            head[m[lb[l][0]]]=0;//如果是小组最后一个元素，就记录小组为空
            l=lb[l][1];
        }
    }
    return 0;
}