Skip to content

11607: 【原1607】天真队列

题目

题目描述

author: Chika 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1607 ## Description

在这个奇怪的时代，你往往要将人们天真的需求实现成一个个数据结构。

假想这样一个场景，有一些人希望制定一系列潜在的规则来对人们的行为进行一定的约束，产生的原则之一便是先来后到。

但是天真的人们自然用他们自己的眼光来看待这样一种规则，他们认为，如果当前的队列中有与其关系很好的人(不如称为一个小团体)，那么便可以毫无顾忌的站在 当前队列最靠后的那个小团体的人的后面，用一种占位子的天真借口。而那些因此想法而未得到好处的人(队列中没有关系好的人)，便只能老实的排在最后面。

现在你要做的，就是在人们的天真的想法之下，将这个日常平凡的过程再现出来。

Input Format

第一行是一个数n，表示参与排队的人的个数。

第二行将会读入n个非负整数，每一个整数表示这个人所属的团体的id，这个id是按照时序给出的。

第三行是一个数q，代表可能的事件数。

接下来q行，每一行代表一种可能的事件。

  • 0: 来了一个新人。如果每一个人都曾经入过一次队列了，你应当忽略这个操作。
  • 1: 队首的人离开了，请输出这个人的编号。如果队列空了，你应当输出"-1"。

Output Format

对于每一个询问类事件，输出对应的答案或者是"-1"。

Sample Input

2
1 2
2
0
1

Sample Output

1

Limits

  • 对于50%的数据，n, q <= 4000
  • 对于100%的数据，n, q <= 2000000, 每个人所属的团体id满足0 <= id <= 10^9

Pangbo13's solution 

#include<iostream>
#include<queue>
#include<map>
using namespace std;

int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x  = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
class naive_queue{
    map<int,queue<int>> pos;
    queue<int> group;
    public:
        naive_queue(){};
        void push(int group_id,int person_id){
            auto p = pos.find(group_id);
            if(p == pos.end()){
                p = pos.insert(pair<int,queue<int>>(group_id,{})).first;
            }
            queue<int>& q = (*p).second;
            if(q.empty()){
                group.push(group_id);
            }
            q.push(person_id);
        }
        int pop(){
            auto q = pos.find(group.front());
            int ans = (*q).second.front();
            (*q).second.pop();
            if((*q).second.empty()){
                group.pop();
            }
            return ans;
        }
        int front(){
            auto q = pos.find(group.front());
            return (*q).second.front();
        }
        bool empty(){
            return group.empty();
        }
};

int main(){
    int* buffer;
    naive_queue nq;
    int n,q,front = 0,person_id = 1;
    n = read();
    buffer = new int[n];
    for(int i = 0;i<n;i++){
        buffer[i] = read();
    }
    q = read();
    for(int i = 0;i<q;i++){
        int choice;
        choice = read();
        switch(choice){
            case 0:
                if(front < n){
                    nq.push(buffer[front],person_id);
                    ++ front;
                    ++ person_id;
                }
                break;
            case 1:
                if(nq.empty()){
                    printf("-1\n");
                }else{
                    printf("%d\n",nq.pop());
                }
                break;
        }
    }
    delete[] buffer;
}

q4x3's solution 

/**
 * 全wa了
 * 不写了
 * 题意理解错了属实拉跨
 **/
#include <iostream>
#include <stdio.h>
#define re register

using namespace std;

inline void read(int &x) {
    x = 0;
    char ch;
    bool f = 0; 
    while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = 1;
    else x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
    x = f ? -x : x;
}

int p[2000233], n, query, op, idq[2000233], numq[2000233], rear, pnum, head, qcur;
// int p[200], n, query, op, idq[200], numq[200], idnum, pnum, head, qcur;
inline int find(const int &x) {
    for(re int i = head;i < rear;++ i) {
        if(idq[i] == x) return i;
    }
    return -1;
}

int main() {
    read(n);
    for(re int i = 0;i < n;++ i) {
        read(p[i]);
    }
    read(query);
    for(int i = 0;i < query;++ i) {
        read(op);
        if(!op) {
            if(pnum == n) continue;
            else {
                int tmp = find(p[pnum]);
                ++ qcur;
                if(tmp == -1) {
                    ++ numq[rear];
                    idq[rear ++] = p[pnum ++];
                } else {
                    ++ pnum;
                    ++ numq[tmp];
                }
            }
        } else {
            if(qcur) {
                printf("%d\n", idq[head]);
                -- qcur;
                -- numq[head];
                if(!numq[head]) {
                    ++ head;
                }
            } else {
                printf("%d\n", -1);
            }
        }
    }
    return 0;
}

satgo1546's solution 

#include <map>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct node {
    int g; // 团体号
    int next; // 链式队列中下一个节点的下标
};

int n;
// 通过在数组里链接下标的方式来实现链式队列的同时，避免了new和delete。
node a[2000005];
int head = -1;
int tail = -1;
// 下一个要入队的人的下标。
int outer = 0;
// 记录每个团体末尾是谁，a[grouptail[团体号]]就是团体末尾的那个node。
map<int, int> grouptail;

int main(int argc, char *argv[]) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i].g);
        a[i].next = -1;
    }
    scanf("%d", &argc);
    while (argc--) {
        int op;
        scanf("%d", &op);
        if (op) {
            // 出队。
            if (head < 0) {
                puts("-1");
                continue;
            }
            // 输出的“编号”是指此人第几个入队。
            printf("%d\n", head + 1);
            if (grouptail[a[head].g] == head) {
                grouptail.erase(a[head].g);
            }
            head = a[head].next;
            if (head < 0) tail = -1;
        } else {
            // 入队。
            if (outer >= n) continue;
            if (head < 0) {
                head = tail = outer;
                grouptail[a[outer].g] = outer;
            } else {
                // 找一团体号相同的组的尾巴。
                int ind = tail;
                if (grouptail.find(a[outer].g) != grouptail.end()) ind = grouptail[a[outer].g];
                a[outer].next = a[ind].next;
                a[ind].next = outer;
                if (a[outer].next < 0) tail = outer;
                grouptail[a[outer].g] = outer;
            }
            outer++;
        }
        // 调试用输出。
        if (0) {
            for (int ind = 0; ind < n; ind++) {
                printf("[%2d] %4d %2d ", ind, a[ind].g, a[ind].next);
                if (ind == head) printf(" head");
                if (ind == tail) printf(" tail");
                if (ind == outer) printf(" outer");
                printf("\n");
            }
            int ind = head;
            while (ind >= 0) {
                printf("%d ", a[ind].g);
                ind = a[ind].next;
            }
            putchar('\n');
        }
    }
    return 0;
}