题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=481
题目类型: 数据结构, 二叉树
样例输入:
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
样例输出:
Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001
题目大意:
有个所谓的team排序, 给出t个队伍,以及这些队伍的成员。 然后进行排队。
ENQUEUE x: 把x插入队列中时。如果队列没有该元素的队员,则插入队列的最后面。如果队列中已经有了他的队员,那么插入最后一个队员之后。
DEQUEUE: 把队头的元素删除,并且输出
STOP: 停止
解题思路:
如果对链表熟悉,要模拟这个过程并不难。 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\n", 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\n", cas++);
Solve();
printf("\n");
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
前端开源库-promise-queue-plusPromise Queue Plus,基于Promise的队列。支持超时、重试等。
前端开源库-promise-queue承诺队列,基于承诺的队列
Priority Job Queue is an implementation of a Job Queue specifically written for Android to easily schedule jobs (tasks) that run in the background, improving UX and application stability.
基于C语言的数据结构-队列queue
基于python的数据结构代码实现-队列Queue
Queue-Queue-Queue
Windows Azure的MSMQ--Queue Storage 例子 Windows Azure的MSMQ--Queue Storage 例子
离线安装包,亲测可用
Lock-free Queue and Ring Buffer
Laravel开发-laravel-queue-aws-batch 用于AWS批处理的Laravel队列,允许用户将作业提交到批处理队列进行处理。
single-producer, single-consumer lock-free queue
Android¦-Message Queue
修复android-priority-jobqueue-2.0.1这个开源库cursor没关闭的BUG
微小的队列数据结构 如果在大型数组上执行大量Array#push()和Array#shift() ,则应使用此包而不是数组,因为Array#shift()具有O(n),而Queue#dequeue()具有O(1) 。 对于大型阵列,这有很大的不同。 是元素的...
前端项目-jquery-ajaxQueue,A simple queue for ajax requests
Laravel开发-laravel-async-queue Laravel的异步队列驱动程序(推到后台)
离线安装包,亲测可用
tp5.1安装使用think-queue,处理任务,在readme.md文件里有详细的步骤
前端项目-d3-queue,使用可配置的并发性评估异步任务。