G : 排队援救
Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 69 Solved: 22
Description
突发重大灾难，n个人陷入困境，有一个救援点需要人们排队准备接受救援，假设每个人有一个名望值，进队规则如下：
第一个人直接进队；
当队里已经有人时，新来的人发现队尾的人的名望值比自己大或者相等，他会选择离开去其他救援点；
队伍最多5人，如果一个人要进队时，发现队伍已满，而且他的名望值比队尾的人大，他会选择把队首的人挤掉而继续排在队尾。
问最后得到救援的人分别是谁。Input 单组数据。
第一行为n（1 ≤ n ≤ 100），n为正整数。
第二行为n个人的名望值，第i个去排队的人的名望值为ai （1 ≤ ai≤ 232 - 1），且为正整数。
Output
按顺序输出最后得到救援的人的号码，一个人号码是多少即为他是第几个去排队的。
Sample Input
6
1 3 5 7 9 11Sample Output
2 3 4 5 6
Hint
一、题目大意
设计一个队列模仿，进队，出队，获取当前队列的队尾数值，获取队列的大小，判断队列是否为空。
二、思路
1、储备知识
队列原则：先入先出
a.队列相关的五个函数
| 函数 | 功能 | 例子 |
|---|---|---|
| push() | 入队 | queue< int> qu;qu.push(5)，qu.push(2)，qu.push(0);。则队列里面就有三个数: 5 ,2,0 |
| pop() | 出队 | qu.pop()后，则现在队列只剩2,0 |
| back() | 返回队尾值 | 此时：qu.back()=0 |
| size() | 返回队列长度 | 此时：qu.size()=2 |
| empty() | 判断队列是否为空 | 此时：qu.empty()=0,表示队列不为空，这一般用于循环取出队列值 |
注1：头文件：#include
注2：出队的时候需要保证队列不为空
注3：队列实际是一个模板类，初始化的时候需要指定类型，可以是基础类型也可以是自定义类型。如上文中的：queuequ；
b.映射map相关功能的实现
map
映射相当于f(key)->value,类似一个函数
| 功能 | 例子 |
|---|---|
| 初始化 | mapma;//建立了一个int到int的映射 |
| 增/改 | 直接当做左值即可，ma[3]=2，默认ma[3]=0 |
| 删 | ma[3]=0 |
| 查 | ma[3]，对ma[3]进行操作就行了 |
注1：头文件#include
注2：初始化后，如果value为整数，默认value为0
2、思路
每输入一个声望进行判断
第一步：为每个声望值所代表的人进行编号
第二步：如果队列为空，或者新输入的值大于队尾，则插入
第三步：如果队列大小超过5人则执行出队操作
循环结束后，在对取出队列中的数，对每个数查找对应编号即可
#include<iostream>
#include<map>
#include<queue>
using namespace std;
int main()
{
map<int,int>ma;
queue<int>qu;
int n,num;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>num;
if(!ma[num])ma[num]=i; //如果之前没有记录过，就记录声望值num是第几个排队的人
if(qu.empty()||num>qu.back()) qu.push(num); //如果队列是空的或者队尾的数字比num小，就进队
if(qu.size()>5)qu.pop(); //如果救援队列大于五就弹出
}
while(!qu.empty())
{
cout<<ma[qu.front()]<<" ";
qu.pop();
}
return 0;
}
