优先队列priority_queue

用法详解点这里

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

定义

//升序序列priority_queue,greater > qg;//降序序列priority_queue,less > ql;

银行大厅排队

描述：

在银行营业大厅共服务3种客户，类型为A\B\C，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。

输入：

第一行输入先输入n表示客户数量
第二行输入每个客户的类型，数据之间用用空格隔开
第三行输入每个客户的办理时间，数据之间用用空格隔开

/示例/
8
A B C B C A A A
10 20 30 40 50 60 70 80
1
2
3
4
输出：

第一行输出A类客户的平均办理时间 ：
第二行输出B类客户的平均办理时间 :20+40=60/2=30
第三行输出C类客户的平均办理时间

/示例/
55
30
40
解题思路：

为了算出各类客户的平均办理时间，首先要知道的是各类客户花费的总时间。

3种窗口服务三种客户，也就是算出每个窗口的时间。通过将每个窗口抽象成一个队列，将时间作为内容填入队列，即可算出总时间。

除了每个窗口的队列以外，我们还需要将输入的顺序进行存储，因此总共需要4条队列。

#include
#include
using namespace std;int main() {int t;  //次数int m;  //待输入的时间char ch;  //待输入的客户类型queue myQe, myQa[3];  // Qe代表次序，Qa代表窗口cin >> t;// 输入部分while (t--) {cin >> ch;myQe.push(ch-65);  //注意此处push进去的是一个数字，为了查找方便，当ch=A时，把0给push进去，以此类推。A字符转化为数字为65}//输入部分while (!myQe.empty()) {cin >> m;int num = myQe.front();  //根据顺序获取窗口myQe.pop();myQa[num].push(m);}//输出部分for (int i = 0; i < 3; i++) {int n = myQa[i].size();  //计算平均数时需要的分母int sum = 0;while (!myQa[i].empty()) {sum += myQa[i].front();myQa[i].pop();}cout << sum / n << endl;}
}

训练挑战

#include
#include
using namespace std;int main() {int t;  //次数int m;  //待输入的时间char ch;  //待输入的客户类型queue myQe, myQa[3];  // Qe代表次序，Qa代表窗口cin >> t;// 输入部分while (t--) {cin >> ch;; //注意此处push进去的是一个数字，为了查找方便，当ch=A时，把0给push进去，以此类推。A字符转化为数字为65}//输入部分while (!myQe.empty()) {cin >> m;int num = myQe.front();  //根据顺序获取窗口;//myQe弹出;//myQa[num]入队列m}//输出部分for (int i = 0; i < 3; i++) {int n = myQa[i].size();  //计算平均数时需要的分母;//定义num，并初始化while () {//判断myQa[i]是否为空;//sum加上当前myQa[i]的值;//myQa[i]弹出};//输出 sum 除以 n 答案 }
}