UVa 540：Team Queue 数据结构专题

UVa 540：Team Queue 数据结构专题2014-10-06 shuangde800 题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=481

题目类型：数据结构，二叉树

样例输入：

23 101 102 1033 201 202 203ENQUEUE 101ENQUEUE 201ENQUEUE 102ENQUEUE 202ENQUEUE 103ENQUEUE 203DEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25 259001 259002 259003 259004 2590056 260001 260002 260003 260004 260005 260006ENQUEUE 259001ENQUEUE 260001ENQUEUE 259002ENQUEUE 259003ENQUEUE 259004ENQUEUE 259005DEQUEUEDEQUEUEENQUEUE 260002ENQUEUE 260003DEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP0

样例输出：

Scenario #1101102103201202203Scenario #2259001259002259003259004259005260001

题目大意：

有个所谓的team排序，给出t个队伍，以及这些队伍的成员。然后进行排队。

ENQUEUE x: 把x插入队列中时。如果队列没有该元素的队员，则插入队列的最后面。如果队列中已经有了他的队员，那么插入最后一个队员之后。

DEQUEUE：把队头的元素删除，并且输出

STOP：停止

解题思路：

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45535.htm

如果对链表熟悉，要模拟这个过程并不难。 STL 中的list挺好用的，是双向循环链表。 end（）成员函数返回链接首位的那个迭代其。题目的一个关键过程是进行查询元素x时属于哪个队伍（可以用二分查找加速，提高的速度很客观），还可以开一个超大的数组，用坐标映射元素值，数组保存队伍号，这样的话查找元素的队伍只需要O（1）的时间，是最快的。然后更关键的一步是，每次插入位置的查找，如果每次的插入都要进行查找一次位置，肯定会TLE。可以另外开一个迭代器数组保存某队伍在队列中的最后一个位置的迭代器。

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<list>#include<string>#include<algorithm>using namespace std;int t, commandNum,posTeam;int team[1005][1005];char command[10];list<int>m_list;list<int>::iterator lastIt[1005];int ele[1000000];// 用来来映射元素属于哪个队伍。下标对应元素值// 查找这个数在哪个队伍。 int SearchTeam（int num）{int i,j;for（i=0; i<t; ++i）{// 二分查找if（binary_search（team[i]+1, team[i]+1+team[i][0], num））return i;}//如果查不到，返回-1. 其实题目给的元素一定时属于某一队的，是我想复杂了return -1; }void Input（）{int i,j;for（i=0; i<t; ++i）{scanf（"%d", &team[i][0]）;for（j=1; j<=team[i][0]; ++j）{scanf（"%d",&team[i][j]）;ele[team[i][j]] = i;}lastIt[i] = m_list.end（）;// 进行排序，为二分做准备sort（team[i]+1, team[i]+1+team[i][0]）;}}// 入队void Enqueue（int num）{posTeam=SearchTeam（num）;// 用下面这种的方法获得队伍速度更加快//posTeam = ele[num];if（lastIt[posTeam] == m_list.end（））{// 在m_list.end（）中插入，效果和push_back一样lastIt[posTeam] = m_list.insert（lastIt[posTeam], num）; }else{ ++lastIt[posTeam];lastIt[posTeam] = m_list.insert（lastIt[posTeam], num）; } }void Dequeue（）{if（m_list.empty（）） return;printf（"%d
", m_list.front（））; list<int>::iterator it = lastIt[m_list.front（）];// 如果弹出的那个元素是队列中剩下的队伍中的最后一个，要相应的修改for（int i=0; i<t; ++i）{if（lastIt[i]==m_list.begin（））{lastIt[i] = m_list.end（）;break;}}m_list.pop_front（）;}void Solve（）{if（！m_list.empty（）） m_list.clear（）;while（~scanf（"%s",command））{if（！strcmp（command, "STOP"）） break;if（！strcmp（command,"ENQUEUE"））{scanf（"%d",&commandNum）;Enqueue（commandNum）;}else if（！strcmp（command,"DEQUEUE"））{Dequeue（）;}}}int main（）{freopen（"input.txt","r",stdin）;int cas=1;while（~scanf（"%d",&t） && t）{Input（）;printf（"Scenario #%d
", cas++）;Solve（）;printf（"
"）;} return 0;}