P2776 [SDOI2007]小组队列题解

需要解决的问题

• 1.如何将小组中的元素插进去?

• 2.如何按顺序输入。

思路

显然，这个题的名字就是小组队列，并根据题意及样例，我们可以比较容易的想到队列这个东西。

首先我们知道，用一个队列肯定是不行的，因为队列不支持从中间插入一个数值；之后我们就看数据范围： \(n \leq 10^6\) ，\(m \leq 300\) 。那么我么转换思路，把每一个小组都当成一个队列，再单独给一个队列存储小组之间的顺序，这样，在我们输出的时候就按顺序输出就行了，如果这个小组里面的元素被弹空了，我们就把这个小组从队列中弹出。

注意事项

• 1.元素和小组的编号都是从 \(0\) 开始；

• 2.if 语句的位置

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,t;
string st;
int group[100005];

queue <int> order;/*小组的顺序*/ 
queue <int> q[305];/*小组里元素的顺序*/ 

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n-1;i++)
		scanf("%d",&group[i]);/*注意从0开始，输入该元素所属的小组*/ 
	int x;
	scanf("%d\n",&t);
	for(int i=1;i<=t;i++)
	{
		cin >> st;
		if(st=="push")
		{
			scanf("%d",&x);
			int number=group[x];/*number存储输入进去的元素所在的小组*/ 
			if(q[number].empty()) order.push(number);/*注意if语句的位置，先判断是否该小组是否还没有元素，是的话就存入order队列中*/ 
			q[number].push(x);/*如果 if 语句在下面，就会导致if语句一定不成立，order里面没有元素，进而导致代码错误*/ 
		}
		if(st=="pop")
		{
			int dl=order.front();/*查找优先级最高的小组，也就是在队头的小组*/ 
			printf("%d\n",q[dl].front());/*输出*/ 
			q[dl].pop();/*弹出该元素*/ 
			if(q[dl].empty()) order.pop();/*如果这个小组空了，那么下一个该小组的元素进来后顺序就得往后边排了。因此，弹出该小组*/ 
		}
	}
	return 0;
}