540 - Team Queue

71 阅读 0 评论 47 点赞

我是靠谱客的博主清脆花生，最近开发中收集的这篇文章主要介绍540 - Team Queue，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：540 - Team Queue

题目大意：就是模拟一个排队，如果在队列中找到同一组的就接在同一个组的元素的后面，在队列中没有找到相同的组的元素纠结在队伍的最后面。

解题思路：给一个数组来模拟队列，这个数组里的每个元素里都有一个子队列，还有这个子队列所属的类别。

给两个元素指向头和尾，构建循环队列。N是队列的最大长度。

进队时，就在对首和对尾间找，找到相同类别的就加入这个子队列，没找到就加入对尾，队尾++%N；

退队时，就从对首退队，对首++%N，并且如果这个子对列空的话，就要使的它的所属类别变成-1，回收；

注意：输入时ENQUEUE x 可能这两个之间可能有多个空格，不能要用gets（）再分离出数据来。

因为我只初始化一个队列，所以每次新的测试数据时，队列要清空。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 1005;
int t;

int s[N][N];
char op[20];
int k = 0;
struct TEAM {

	int id;
	queue<int> q;

} team[N];

int cmp(const int &a, const int &b) {

	return (a > b) ? 0 : 1;
}

int find(int a) {

	int first, mid, last;
	for(int i = 0; i < t; i++) {

		first = 1;
		last = s[i][0];
		while(first <= last) {

			mid = (first + last) /2;
			if(s[i][mid] == a)
				return i;
			else if(s[i][mid] > a)
				last = mid - 1;
			else
				first = mid + 1;
		}
	}		
}

int main() {

	while(scanf("%d", &t) && t) {

		k++;
		memset(s, 0, sizeof(s));
		printf("Scenario #%dn", k);
		int i, j, n;
		for(i = 0; i < t; i++) {

			scanf("%d", &n);
			s[i][0] = n; 
			for(j = 1; j <= n; j++) {

				scanf("%d", &s[i][j]);
			}
		}
		scanf("%*c");
		for(i = 0; i < t; i++)  {

			sort(&s[i][1], &s[i][1]  + s[i][0], cmp);
		}
		for(i = 0; i < t; i++)
			team[i].id = -1;
	int f = 0, l = 0;
	while(scanf("%s", &op) ) {

		if(strncmp(op, "ENQUEUE", 7) == 0) {

			int num ;
			scanf("%d", &num);
			j = find(num);
			for(i = f; i != l ; i = (i + 1) % N) {

				if(team[i].id != -1 && team[i].id == j) {

					team[i].q.push(num);
					break;
				}
			}		
			if(i == l) {

					team[l].id = j;
					team[l].q.push(num);
					l = (l + 1) % N;
			}
		}
		else if(strncmp(op, "DEQUEUE", 7) == 0) {
				
				if(!team[f].q.empty()) {

					printf("%dn", team[f].q.front());
					team[f].q.pop();
					if(team[f].q.empty()) {

						team[f].id = -1;
						f = (f + 1 ) % N;
						
					}
				}
		}
		else  {

			for(i = f; i != l; i = (i + 1) % N)
				while(!team[i].q.empty()) {
					
					team[i].q.pop();
				}

			printf("n");
			break;
			
			}
		memset(op, 0, sizeof(op));
	
		}
	}
	
	return 0;
}