没时间了,而且自己不知道用法,脑子又愚钝,所以就理解下代码就好了
http://acm.hust.edu.cn/vjudge/contest/128220#problem/F
以下源代码
——————————————————————————————————
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
const int maxt=1000+10;
int main()
{
int t,kase=0; //kase时因为输出格式所以jia'de
while(scanf("%d",&t)==1&&t) //判断种植条件
{
printf("Scenario #%d\n",++kase); //格式
map<int,int> team; //创建一个映射 相同队列的人对应同一个value值
for(int i=0;i<t;i++) //输入队列人数(一队一队输)
{
int n,x;
scanf("%d",&n);
while(n--)
{
scanf("%d",&x); //输入人
team[x]=i; //映射进i 同一队在同一for循环输入 i相同
}
}
queue<int> q,q2[maxt]; //q为队列的队列 , q2[i]是x成员所在队列 每一个不同的i代表不同队列
for(;;) //一直循环 直到输入S break;
{
int x;
char cmd[10]; 原题里有这个:Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation
of the team queue should be efficient: both enqueing and dequeuing of an element should
only take constant time. 所以我不是很理解这里开到10是什么意思
scanf("%s",cmd); //输入指令 判断首字母 如果需要整体判断 之前有用过string
if(cmd[0]=='S') break;
else if(cmd[0]=='D')
{
int t=q.front(); //令t = 总队列中的支队列(用唯一映射的int代表,并不是真正地包含)
printf("%d\n",q2[t].front());
q2[t].pop(); //删除首队伍中的首元素
if(q2[t].empty()) q.pop(); //支队列为空则删除
}
else if(cmd[0]=='E')
{
scanf("%d",&x);
int t=team[x];
if(q2[t].empty()) q.push(t);
q2[t].push(x);
}
}
printf("\n");
}
return 0;
}
题目明确告诉了我们使用队列。使用一个队列排列团队;再使用一个队列排列元素。题目中说了出队入队只能花费常数时间,所以要在元素和团队之间建立映射关系而不能简单地使用数组存下元素。
在这样队中有队的关系中,大的队中不是真的包含着队列,而是一个具有唯一性的数据
push()会将一个元素置入queue中。
front()会返回queue内的第一个元素(也就是第一个被置入的元素)。
back()会返回queue中最后一个元素(也就是最后被插入的元素)。
top()取队首元素(但不删除)。
pop()会从queue中移除一个元素。
注意:pop()虽然会移除下一个元素,但是并不返回它,front()和back()返回下一个元素但并不移除该元素。
另:
优先队列也定义在头文件中,用"priority_quene pq"来声明。(越小的整数优先级越低)
由于出队的元素并不是最先进队的元素,出队的方法由front()变为了top().
越小的整数优先级越大的定义方式 "priority_queue<int,vector,greater > pq"
自定义类型也可以组成优先级队列,但必须为每个元素定义一个优先级。
eg. 实现 “个位数的的整数优先级反而小” ,可以定义一个结构体cmp,重载“()” 运算符,然后用“priority_queue<int,vector,cmp> pq"的方式定义
下面是cmp的定义
struct cmp{
bool operator() (const int a, const int b)const{ //a的优先级比b小时返回true
return a%10>b%10;
}
}
另外 队与栈的区别 https://zhidao.baidu.com/question/223432364.html
question: 要多层嵌套队列要怎么做?