想請問neoj上的題目-中國人排隊問題 | 中學資訊討論群 CISC | Page 1

twilit knoll Mar 30, 2023, 11:48 AM

#

https://neoj.sprout.tw/problem/20/

#

等窩一下

#

我打一下我的作法

#

題目簡述:有一堆人要排隊，其中有一些人是「同夥的」，而一團同夥的人成為「一團」人。在一個人要排進隊伍時，如果在隊伍中他有「同夥」，他可以要求「給個方便」，而直接排在他的同夥們後面，如果他沒有同夥，那他只能乖乖從最後開始排隊。

#

我的解法:因為一個人不會隸屬兩團中國人，所以我想到並查集，於是我開了一個陣列dsu，紀錄每個人在哪一團。然後我開了一個長度為1010的queue陣列(以arr,heads,tails三個陣列和head,tail兩個變數實作)，在一個人要進入隊伍前，我會先判斷隊伍中有沒有人跟他是同夥的(我開了另一個陣列place，index代表某團，而index的值代表這團在queue陣列中的位置)，如果有(place中，以這個人隸屬的團為index，其值不是-1)，我就往queue陣列中對應的queue(queue陣列的index為place中，以這個人隸屬的團為index的值)塞入這個人，如果沒有(place中，以這個人隸屬的團為index，其值是-1)，那我就把這個人塞入有塞人的所有queue的後一個queue(tail會紀錄queue陣列中有塞人的所有queue後一個queue的位置)，並且在place中，以這個人隸屬的團為index，紀錄這個在queue陣列中塞入的位置，最後tail增加1，指到下一個沒有塞人的queue。當前面的人要離開隊伍時，先輸出queue陣列中最前面的人的位置，如果queue陣列中最前面的人所屬的queue只有一個人，輸出後,head增加1，代表往下一個陣列當最前面人隸屬的queue。

#

#include<bits/stdc++.h>
using namespace std;
int dsu[1000010];
//queue in queue
//queue<int> arr[1010];//representing the line where people in
int arr[1100010];
int heads[1010],tails[1010];
int head=0,tail=0;
//representing where the group in line,index represent group,value represent place
int place[1010];

void push(int a){
    int group=dsu[a];
    if(place[group]==-1){
        place[group]=tail++;
    }
    if(tail==1005)tail=0;
    arr[tails[place[group]]]=a;
    tails[place[group]]++;
    return;
}

void pop(){
    if(heads[head]+1==tails[head]){
        place[dsu[arr[heads[head] ] ] ]=-1;
        cout<<arr[heads[head] ]<<"\n";
        heads[head]=0+head*1010;
        tails[head]=0+head*1010;
        head++;
        //heads[head]++;
    }else{
        cout<<arr[heads[head] ]<<"\n";
        heads[head]++;
        //arr[head].pop();
    }
    if(head==1005)head=0;
}

void solve(){
    //refill the place and arr
    for(int i=0;i<1010;i++){
        place[i]=-1;
        heads[i]=0+i*1010;
        tails[i]=0+i*1010;
    }
    /*
    for(int i=0;i<1010;i++){
        if(arr[i].size()>0)place[dsu[arr[i].front()]]=-1;
        while(arr[i].size()>0)arr[i].pop();
    }
    */
    int n;
    cin>>n;
    //allocating people in groups
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=0;j<m;j++){
            int tmp;
            cin>>tmp;
            dsu[tmp]=i;
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        if(tmp=="ENQUEUE"){
            int a;
            cin>>a;
            push(a);
        }else{
            pop();
        }
    }
    return;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    int a=0;
    while(a!=t){
        cout<<"Line #"<<a+1<<"\n";
        solve();
        a++;
    }
    return 0;
}

#

我這題一直卡WA

#

但是我找不到bug qq

vital stag Mar 30, 2023, 11:53 AM

#

感覺可以用 queue 就好耶

#

si_cookie

twilit knoll Mar 30, 2023, 11:53 AM

#

怎麼說?

vital stag Mar 30, 2023, 11:53 AM

#

就他就是一個大的 queue 包小的 queue

#

不確定我又沒有看錯題目

twilit knoll Mar 30, 2023, 11:54 AM

#

可是在大queue裡後面的queue有塞人時，前面的queue之後可能也會塞人

#

把人全部抽出來重塞一次可能會TLE

vital stag Mar 30, 2023, 11:55 AM

#

那就用陣列包 queue

#

happy_mention

#

這樣就可以 O(1) 更新小 queue

#

記錄一下 index 就好了

twilit knoll Mar 30, 2023, 11:57 AM

#

你是說用陣列包一堆queue，然後陣列兩個變數紀錄陣列裡最前面有塞人的queue和最後面有塞人的queue嗎?

vital stag Mar 30, 2023, 11:58 AM

#

對

twilit knoll Mar 30, 2023, 11:59 AM

#

那我的作法跟你想一樣

#

只是我的queue是用實作弄出來的

#

我嘗試用過STL，但是被RE了(

twilit knoll Mar 30, 2023, 3:07 PM

#

我剛剛突然想到

#

會不會是我的輸出整理錯誤

#

最後面要少一個換行

#

但是

#

還是錯(

#

#include<bits/stdc++.h>
using namespace std;
int dsu[1000010];
//queue in queue
//queue<int> arr[1010];//representing the line where people in
int arr[1100010];
int heads[1010],tails[1010];
int head=0,tail=0;
//representing where the group in line,index represent group,value represent place
int place[1010];

void push(int a){
    int group=dsu[a];
    if(place[group]==-1){
        place[group]=tail++;
    }
    if(tail==1005)tail=0;
    arr[tails[place[group]]]=a;
    tails[place[group]]++;
    return;
}

void pop(){
    if(heads[head]+1==tails[head]){
        place[dsu[arr[heads[head] ] ] ]=-1;
        cout<<"\n"<<arr[heads[head] ];
        heads[head]=0+head*1010;
        tails[head]=0+head*1010;
        head++;
        //heads[head]++;
    }else{
        cout<<"\n"<<arr[heads[head] ];
        heads[head]++;
        //arr[head].pop();
    }
    if(head==1005)head=0;
}

void solve(){
    //refill the place and arr
    for(int i=0;i<1010;i++){
        place[i]=-1;
        heads[i]=0+i*1010;
        tails[i]=0+i*1010;
    }
    /*
    for(int i=0;i<1010;i++){
        if(arr[i].size()>0)place[dsu[arr[i].front()]]=-1;
        while(arr[i].size()>0)arr[i].pop();
    }
    */
    int n;
    cin>>n;
    //allocating people in groups
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=0;j<m;j++){
            int tmp;
            cin>>tmp;
            dsu[tmp]=i;
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        if(tmp=="ENQUEUE"){
            int a;
            cin>>a;
            push(a);
        }else{
            pop();
        }
    }
    return;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    int a=0;
    bool door=false;
    while(a!=t){
        if(door)cout<<"\n";
        door=true;
        cout<<"Line #"<<a+1;
        solve();
        a++;
    }
    return 0;
}

#

改過的程式碼

umbral elk Mar 30, 2023, 3:11 PM

#

草，我眼殘

twilit knoll Mar 30, 2023, 3:15 PM

#

?

#

甚麼眼殘

umbral elk Mar 30, 2023, 3:16 PM

#

我剛剛叫你重看範測，然後才發現是自己看錯題目 EEEEE

twilit knoll Mar 30, 2023, 3:17 PM

#

happythonk

#

看來你需要rad bull

umbral elk Mar 30, 2023, 3:18 PM

#

happythonk

twilit knoll Mar 30, 2023, 3:22 PM

#

請你喝

#

低成本red bull

umbral elk Mar 30, 2023, 4:48 PM

#

AC了

#

這題的題目也是挺可怕的ㄟ

#

我一開始只發現你的程式若上一次輸入中沒有讓所有排隊的人都有離開隊伍(拿到公仔)，那下一次詢問就會出錯

#

結果改了沒過，我去看了一下這題的提交狀況，幾乎所有都是WA
所以我猜可能是題目有陷阱或者大家會不小心預設某種前提之類的
結果就發現問題了

#

我覺得挺有趣的你可以自己找找看(範測的第一筆資測可以看出問題

twilit knoll Mar 30, 2023, 4:57 PM

#

🛐

#

那我要來找問題了ouob

#

我一直以為是我程式碼有bug

#

你這樣一說

#

我好像有些方向了

#

感謝ouob

#

如果我想不出來的話再來這邊求救douob

twilit knoll Mar 30, 2023, 5:00 PM

#

umbral elk 我一開始只發現你的程式若上一次輸入中沒有讓所有排隊的人都有離開隊伍(拿到公仔)，那下一次詢問就會出錯

for(int i=0;i<1010;i++){
        place[i]=-1;
        heads[i]=0+i*1010;
        tails[i]=0+i*1010;
    }

#

備註:這個是用來清空queue陣列的

umbral elk Mar 30, 2023, 5:05 PM

#

問題應該是你的head跟tail吧
跑這組可以看出來
2
1
1 1
1
ENQUEUE 1
1
1 2
2
ENQUEUE 2
DEQUEUE

twilit knoll Mar 30, 2023, 5:06 PM

#

草

#

我忘記那兩個東西了ww

#

#

突然發現一件有趣的事

#

第三種敘述不見了

twilit knoll Mar 30, 2023, 5:37 PM

#

#

我要哭了

#

這題我解了5天

#想請問neoj上的題目-中國人排隊問題