题解：UVA12207 That is Your Queue

海洋守卫者 · 2025-05-06 16:47:27 · 题解

UVA12207 That is Your Queue

解题思路

容易发现，对于病人序号的访问是环状的，且中间有插入和删除操作，因此可以使用环状双向链表。

考虑到 1\le p\le 10^9，建如此庞大的链表似乎不合适。然而，可以发现，当 c\le p 时，访问不会是环装的，因为操作次数不可能将所有病人序号全都访问一遍。

进行分类讨论。当 p<c 时，使用环状双向链表，大小不会超过 3000；当 c\le p 时，用 map 记录是否病人已经被访问，用栈记录被提前安置的病人。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stack>
#include<map>
using namespace std;
struct Node{
    int id;
    Node *lst,*nxt;
}p[3006],*head;
int n,c,cases=0;
map<int,bool>m;
stack<int>st;
int main()
{
    while(~scanf("%d %d",&n,&c))
    {
        if(n+c==0)return 0;
        printf("Case %d:\n",++cases);
        if(c>n)
        {
            head=&p[0];
            for(int i=0;i<n;i++)
            {
                p[i].id=i+1;
                p[i].nxt=&p[(i+1)%n];
                p[i].lst=&p[(i+n-1)%n];
            }
            for(int i=1;i<=c;i++)
            {
                char opt;
                scanf("\n%c",&opt);
                if(opt=='N')
                {
                    printf("%d\n",head->id);
                    head=head->nxt;
                }
                else{
                    int x;
                    scanf("%d",&x);--x;
                    if(head==&p[x])continue;
                    p[x].lst->nxt=p[x].nxt;
                    p[x].nxt->lst=p[x].lst;
                    head->lst->nxt=&p[x];
                    p[x].lst=head->lst;
                    head->lst=&p[x];
                    p[x].nxt=head;
                    head=head->lst;
                }
            }
        }
        else{
            while(!st.empty())st.pop();
            m.clear();
            char opt;
            int h=1;
            for(int i=1;i<=c;i++)
            {
                scanf("\n%c",&opt);
                while(!st.empty()&&m[st.top()])st.pop();
                if(opt=='N'){
                    if(st.empty())
                    {
                        while(m[h])h++;
                        m[h]=1;
                        printf("%d\n",h++);
                    }
                    else{
                        if(!m[st.top()])printf("%d\n",st.top());
                        m[st.top()]=1;
                        st.pop();
                    }
                }
                else{
                    int x;
                    scanf("%d",&x);
                    st.push(x);
                    m[x]=0;
                }
            }
        }
    }
    return 0;
}