POJ-2259 Team Queue(模拟+队列)

http://poj.org/problem?id=2259

题意:

在组队队列中,每个元素属于一个队伍。如果一个元素将要进入组队队列时,会从头到尾找它的队友是否已经在队列中,如果找到了,他就会紧随其后进入队伍。如果没有找到,则它会从队列末尾入队,并成为自己队列的第一个元素。出队操作则和普通队列一样:元素在组队队列中按从头到尾的顺序出列

思路:

解决入队问题,如果用一个队列模拟,时间太大,

用team个队列来表示team queue,再用一个队列来保存team前后的信息,再加上一个Flag来标记team是否有元素在team queue中。

代码:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iomanip>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cmath>
#include<stack>

using namespace std;
const int maxn=1e5+10;
const int inf=1e10;
typedef long long ll;

queue<ll> nQue[1001];
queue<int> nS;
int nM[1000000];
bool nFlag[1001];
int nCase=0;
int nNum=0;

void solve()
{
    string nCommand;
    ll nElem;
    cout<<"Scenario #"<<++nCase<<endl;
    while(cin>>nCommand,nCommand!="STOP")
    {
        if(nCommand=="ENQUEUE")
        {
            cin>>nElem;
            if(!nFlag[nM[nElem]])
            {
                nFlag[nM[nElem]]=true;
                nS.push(nM[nElem]);
            }
            nQue[nM[nElem]].push(nElem);
        }
        else if(nCommand=="DEQUEUE")
        {
            int nID=nS.front();
            cout<<nQue[nID].front()<<endl;
            nQue[nID].pop();
            if(nQue[nID].empty()){
                nS.pop();
                nFlag[nID]=false;
            }
        }
    }
    cout<<endl;
}

void init()
{
    for(int i=0; i!=nNum; i++){
        nFlag[i]=false;
        while(!nQue[i].empty()) nQue[i].pop();
    }
    while(!nS.empty()) nS.pop();
}

void input()
{
    int nElem,elemNum;
    for(int i=0; i!=nNum; i++)
    {
        cin>>elemNum;
        for(int j=0; j!=elemNum; ++j)
        {
            cin>>nElem;
            nM[nElem]=i;
        }
    }
}

int main()
{
    while(cin>>nNum,nNum)
    {
        init();
        input();
        solve();
    }
    system("pause");
    return 0;
}

 

上一篇:c++——dynamic_cast < type-id > ( expression)函数用法


下一篇:mysql的InnoDB引擎的行记录格式ROW_FORMAT