【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（9）

矫情吗；* 2022-09-06 00:08 126阅读 0赞

### 文章目录 ###

*  1007 Boring data structure problem 思维+模拟

题目集地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（9）][2021_MINIEYE_9]  
题目集原地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（9）][2021_MINIEYE_9 1]

# 1007 Boring data structure problem 思维+模拟 #

题意：双端队列，给出操作序列，从队列左端插入或者从队列右端插入，删除指定值，询问某一时刻的中位数。  
思路：用两个双端队列模拟，每操作一次对两个队列进行更新，保证右侧队列长度减去左侧队列长度\[0,1\]，用一个数组LR\[\]记录某个数值实在左侧队列还是右侧，用数组del记录某数字是否被删除。每次输出的时候输出右侧队列的队首。  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e7+3;
    deque<int> ql,qr;//左右侧双端队列
    int LR[N];//标记一个数是在左侧还是右侧，1为右侧
    int del[N];//标记一个数是否被删除
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        getchar();
        int num = 1;
        int lsiz = 0,rsiz = 0;//记录左侧队列和右侧队列有效数字的个数
        while(t--)
        { 
            char c = 0;
            scanf("%c",&c);
            getchar();
            switch(c)
            { 
            case 'L':
                ql.push_front(num++);
                lsiz++;
                LR[num-1] = 0;
                break;
            case 'R':
                qr.push_back(num++);
                rsiz++;
                LR[num-1] = 1;
                break;
            case 'G':
                int d;
                scanf("%d",&d);
                getchar();
                del[d] = 1;
                if(LR[d])
                { 
                    rsiz--;
                }
                else
                { 
                    lsiz--;
                }
                break;
            case 'Q':
                while(del[qr.front()])
                { 
                    qr.pop_front();
                }
                printf("%d\n",qr.front());
                break;
            }
            if(lsiz > rsiz)//如果左侧有效数字的数量大于右侧
            { 
                while(del[ql.back()])
                { 
                    ql.pop_back();
                }
                LR[ql.back()]^=1;
                qr.push_front(ql.back());
                ql.pop_back();
                lsiz--;
                rsiz++;
            }
            else if(rsiz > lsiz + 1)
            { 
                while(del[qr.front()])
                { 
                    qr.pop_front();
                }
                LR[qr.front()]^=1;
                ql.push_back(qr.front());
                qr.pop_front();
                lsiz++;
                rsiz--;
            }
        }
        return 0;
    }

[2021_MINIEYE_9]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A89%A3%A9&source=1&searchmode=source
[2021_MINIEYE_9 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=991