hdu 1387 Team Queue （链表）「建议收藏」

全栈程序员-站长 • 2022年1月23日下午8:00 • 未分类 • 阅读 43

大家好，又见面了，我是全栈君。

题目大意：

不同的人在不同的队伍里，插入链表的时候假设这个链表里有他的队友，就把它放到最后一个队友的最后。假设没有队友，就把它放到整个链表的最后面。

出链表的时候把第一个人拿出来。

思路分析：

要模拟这个链表就要记录这整个链表中的队伍存在的情况。

所以要再开一个链表的头指针和尾指针，在整个大的链表中再模拟小区域的链表。

然后就是deque部分，也就是注意head的推断以及更新。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#define maxn 222222
using namespace std;


struct node
{
    int data,next,front;
}list[maxn];
int head[1111];
int tail[1111];
int vis[1111111];
int quenext[1111111];
int listhead;
int listtail;

void print()
{
    int x=listhead;
    while(x)
    {
        printf("%d->",list[x].data);
        x=list[x].next;
    }
    puts("");
}
int main()
{
    int n;
    int CASE=1;
    while(scanf("%d",&n)!=EOF && n)
    {
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
        {
            int t;
            scanf("%d",&t);
            for(int j=0;j<t;j++)
            {
                int a;
                scanf("%d",&a);
                vis[a]=i;
            }
        }

        int num=0;
        listhead=1;
        listtail=1;

        memset(head,0,sizeof head);
        memset(quenext,0,sizeof quenext);
        memset(tail,0,sizeof tail);

        char str[11];
        printf("Scenario #%d\n",CASE++);

        while(scanf("%s",str)!=EOF && str[0]!='S')
        {
            if(str[0]=='E')
            {
                int a;
                scanf("%d",&a);
                int belong=vis[a];

                //printf("---%d\n",head[belong]);

                if(!head[belong])
                {
                    list[listtail].next=++num;
                    listtail=num;
                    list[listtail].next=0;
                    list[num].data=a;
                    head[belong]=tail[belong]=num;
                 //   print();
                    continue;
                }

                list[++num].next=list[tail[belong]].next;
                list[num].data=a;
                list[tail[belong]].next=num;

                if(tail[belong]==listtail)listtail=num;

                quenext[tail[belong]]=num;
                tail[belong]=num;
            }
            else
            {
                int cur=listhead;
                listhead=list[listhead].next;
                int belong=vis[list[cur].data];
                printf("%d\n",list[cur].data);
                head[belong]=quenext[cur];
            }
          //  print();
        }
        puts("");
    }
    return 0;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116267.html原文链接：https://javaforall.net