首页 > 代码库 > UVA540-队列
UVA540-队列
题意:
每一个数字有自己所属的团队,如果所属的团队已经有人在队列里,放在团队的最后一个,要不然放队列里最后一个
注意:一个团队里的最多1000个元素,但是入队,出队的操作会达到200000次
解法:循环队列,声明一个n长的数组,数组的每一个元素都是一个循环队列
没有判断队列是否满了,只简单的判断是否为空
AC时间:570ms
主要耗时在查找元素是那个团队时循环了所有元素,可以简单粗暴使用STL,用了就没意义了,o(︶︿︶)o 唉!!!
#include<iostream>#include <stdio.h>#include <memory.h>using namespace std;struct Node{ int num; int team; Node() { num = -1; team = -1; }};struct Queue{ int ql; Node node[1003]; int position; int limit; Queue() { ql = 1003; position = 0; limit = 0; } void push(Node n) { node[position]=n; position=(position+1)%ql; } Node offer() { Node n= node[limit]; limit=(limit+1)%ql; return n; } bool empty() { return limit == position; }};int findTeam(int number, Node* node, int nl){ for(int i = 0; i < nl; i++) { if(node[i].num == number) { return node[i].team; } } return -1;}int findQueue(int team, Queue*head, int tl){ for(int i = 0; i < tl; i++) { if(head[i].node[0].team == team) { return i; } } return tl;}int main(){ //freopen("d:\\1.txt", "r", stdin); int n; string eq = "ENQUEUE"; string de = "DEQUEUE"; string stop = "STOP"; int t = 0; while (cin >> n) { if(n == 0) return 0; t++; cout << "Scenario #" << t << endl; Node node[n * 1003]; Queue head[n]; int tn = 0; for(int i = 0; i < n; i++) { Queue h; head[i] = h; int m; cin >> m; for(int j = 0; j < m; j++) { Node node2; cin >> node2.num; node2.team = i; node[tn++] = node2; } } string str; int number; int tl = 0; while (true) { cin >> str; if(str == stop) break; else if(str == de) { //de cout << head[0].offer().num << endl; if(head[0].empty()) { int i = 1; for(i = 0; i < tl-1; i++) { head[i] = head[i+1]; } head[tl-1].limit = 0; head[tl-1].position = 0; tl--; } } else { //en cin >> number; int team = findTeam(number, node, tn); int i = findQueue(team,head, tl); Node nn; nn.num = number; nn.team = team; if(head[i].position == 0) tl++; head[i].push(nn); } } cout << endl; } return 0;}
UVA540-队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。