例题5-6 团体队列 UVa540

53 阅读 0 评论 35 点赞

我是靠谱客的博主阳光戒指，最近开发中收集的这篇文章主要介绍例题5-6 团体队列 UVa540，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法竞赛入门经典（第2版）第5章C++与STL入门

例题5-6 团体队列 UVa540

感悟。

1、从网站下载英文原题，重点在看输入输出数据与格式。

2、因队列内容比较熟悉，英文很快看懂，输入输出也没问题。

3、有一个担忧，就是数据量比较大，冒泡排序的查询方式是否会超时。

4、程序想想挺简单，但编起来肯性会有许多细节问题。

5、通过http://blog.csdn.net/chao_xun/article/details/8037438简单学习了queue.

6、瞟了一眼书中中文，发现题意理解有误。If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomesthe new last element (bad luck).这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，他会排到长队的队尾。

7、开辟一个团队队列，开辟一个队列数组。

8、经过一番艰苦的调试，样例通过，在http://vjudge.net第一次提交AC，在https://uva.onlinejudge.org提交AC，看看时间此时2016-11-17 20:45

9、又可以放心的看书中代码了。发现书中将队列用作局部变量，就无需每次清空了。本人思路已与书中代码接近。

附上AC代码，编译环境Dev-C++4.9.9.2

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;

queue<int> q[1000+10];
queue<int> team;
vector<int> vec;
int e[1000+10][1000+10];
int n[1000+10];
int t;
int front;//vector中 front位置

void enqueue(){//入队
    int element;
    int i,j,k;
    int flag=0;
    cin>>element;
    for(i=0;i<t;i++){
        for(j=0;j<n[i];j++)
            if(element==e[i][j]){//查询所在队列
                for(k=front;k<vec.size();k++){
                    if(vec[k]==i)
                        break;
                }
                if(k==vec.size()){//团队数组不存在该队
                    vec.push_back(i);//在团队数组中添加该队
                    team.push(i);
                    q[i].push(element);//在该队中添加元素
                }else//存在该队
                    q[i].push(element);//在该队中添加元素
                //printf("i=%d element=%dn",i,element);
                flag=1;
                break;
            }
        if(flag)
            break;
    }
}

void dequeue(){//出队
    int element;
    int i;
    i=team.front();
    element=q[i].front();
    q[i].pop();
    //printf("i=%dn",i);
    if(q[i].size()==0){//该队列已空
        team.pop();//将该队列从团队中清除。
        front++;//vector右移一个位置.
    }
    cout<<element<<endl;
}
int main(){
    int i,j;
    string cmd;
    int kase=0;
    while(cin>>t&&t){
        front=0;
        vec.clear();//清空数组
        while(team.size())//清空团队队列
            team.pop();
        for(i=0;i<1000+10;i++)//清空队列
            while(q[i].size())
                q[i].pop();
        kase++;
        cout<<"Scenario #"<<kase<<endl;
        for(i=0;i<t;i++){
            cin>>n[i];
            for(j=0;j<n[i];j++){
                cin>>e[i][j];
            }
        }

        while(1){
            cin>>cmd;
            if(cmd[0]=='S')
                break;
            if(cmd[0]=='E'){
                enqueue();
            }else if(cmd[0]=='D'){
                dequeue();
            }
        }
        cout<<endl;
    }
    return 0;
}