随笔-68  评论-10  文章-0  trackbacks-0
UVa 540 - Team Queue
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=481
这道题主要是理解题意。假设有A、B两个班的人到售票处买火车票需要排队，那么每去一个人就站在队列中该班的最后一个人的后面；如果某人是班上第一个去的，则站在队列末尾。相应的每个班对应team, 每个人对应team中的元素，那个排队队列就是题目中的queue.
#include <iostream>
#include <cstdio>
#include <list>
#include <iterator>
#include <list>
using namespace std;

int t;
int ele[1000000];   //记录元素(element)所在的team.
list<int> lst;  //排队队列
list<int>::iterator team[1001]; //指向每个team在lst中排最后一个的元素的位置。若lst中没有team中的元素，则指向lst.end().

int main()
{
    int ca = 0;
    while(cin >> t && t)
    {
        lst.clear();
        int num, tmp;
        for(int i = 1; i <= t; ++i)
        {
            team[i] = lst.end();
            cin >> num;
            for(int j = 0; j < num; ++j)
            {
                cin >> tmp;
                ele[tmp] = i;
            }
        }
        cout << "Scenario #" << ++ca << endl;
        string s;
        while(cin >> s && s != "STOP")
        {
            if(s == "ENQUEUE")
            {
                cin >> tmp;
                if(team[ele[tmp]] != lst.end())
                {
                    ++team[ele[tmp]];
                    team[ele[tmp]] = lst.insert(team[ele[tmp]], tmp);
                }
                else
                {
                    team[ele[tmp]] = lst.insert(team[ele[tmp]], tmp);
                }
            }
            else if(s == "DEQUEUE")
            {
                int top = lst.front();
                if(team[ele[top]] == lst.begin())
                {
                    team[ele[top]] = lst.end();
                }
                lst.pop_front();
                cout << top << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

posted on 2011-11-24 15:38 wuxu 阅读(846) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 wuxu