首页 > 代码库 > 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-队列