本文共 1415 字,大约阅读时间需要 4 分钟。
6740 | 28.95% | 1465 | 77.13% |
题目链接:
题目类型: 数据结构, 二叉树
样例输入:
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: 停止
解题思路:
如果对链表熟悉,要模拟这个过程并不难。 STL 中的list挺好用的, 是双向循环链表。 end()成员函数返回链接首位的那个迭代其。 题目的一个关键过程是进行查询元素x时属于哪个队伍(可以用二分查找加速, 提高的速度很客观),还可以开一个超大的数组,用坐标映射元素值,数组保存队伍号,这样的话查找元素的队伍只需要O(1)的时间,是最快的。 然后更关键的一步是,每次插入位置的查找,如果每次的插入都要进行查找一次位置,肯定会TLE。可以另外开一个迭代器数组保存某队伍在队列中的最后一个位置的迭代器。
代码:
#include#include #include #include #include
#include using namespace std;int t, commandNum,posTeam;int team[1005][1005];char command[10];list m_list;list ::iterator lastIt[1005];int ele[1000000]; // 用来来映射元素属于哪个队伍。下标对应元素值// 查找这个数在哪个队伍。 int SearchTeam(int num){ int i,j; for(i=0; i
转载地址:http://ouzni.baihongyu.com/