王道机试指南 例题5.3 猫狗收容所

题目：

代码：

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

int main(){
    int n;
    cin>>n;
    queue<int> a,at;//a记录狗编号，at记录相应狗的入队时间
    queue<int> b,bt;//b记录猫编号，bt记录相应猫的入队时间
    queue<int> out;//out记录领养顺序
    for(int i=0;i<n;i++){
        int n1,n2;
        cin>>n1>>n2;
        if(n1==1 && n2>0){//狗进入收容所
            a.push(n2);
            at.push(i);
        }
        else if(n1==1 && n2<0){//猫进入收容所
            b.push(n2);
            bt.push(i);
        }
        else if(n1==2 && n2==1){//收养狗
            out.push(a.front());
            a.pop();
            at.pop();
        }
        else if(n1==2 && n2==-1){//收养猫
            out.push(b.front());
            b.pop();
            bt.pop();
        }
        else if(n1==2 && n2==0){//收养最先进入收容所的动物
            if(a.empty()==0 && b.empty()==0){//猫狗队列都不空，则比较队头元素的入队时间
                if(at.front()<bt.front()){
                    out.push(a.front());
                    a.pop();
                    at.pop();
                }
                else{
                    out.push(b.front());
                    b.pop();
                    bt.pop();
                }
            }
            else if(a.empty()==0 && b.empty()==1){//狗队列不空，猫队列空
                out.push(a.front());
                a.pop();
                at.pop();
            }
            else if(a.empty()==1 && b.empty()==0){//狗队列空，猫队列不空
                out.push(b.front());
                b.pop();
                bt.pop();
            }
        }

    }

    while(out.empty()==0){//打印out队列中被收养动物的编号
        cout<<out.front()<<" ";
        out.pop();
    }

    return 0;
}

运行结果：