一本通-1371:看病(优先级队列)¶
【题目描述】 有个朋友在医院工作,想请BSNY帮忙做个登记系统。具体是这样的,最近来医院看病的人越来越多了,因此很多人要排队,只有当空闲时放一批病人看病。但医院的排队不同其他排队,因为多数情况下,需要病情严重的人优先看病,所以希望BSNY设计系统时,以病情的严重情况作为优先级,判断接下来谁可以去看病。
【输入】 第一行输入n,表示有n个操作。
对于每个操作,首先输入push或pop。
push的情况,之后会输入ai 和 bi,分别表示患者姓名和患者病情优先级。
pop后面没有输入,但需要你输出。
【输出】 对于pop的操作,输出此时还在排队人中,优先级最大的患者姓名和优先级。
表示他可以进去看病了。
如果此时没人在排队,那么输出”none”,具体可见样例。
【输入样例】 7 pop push bob 3 push tom 5 push ella 1 pop push zkw 4 pop
【输出样例】 none tom 5 zkw 4
这道题本身不难,奇怪的是使用解除绑定的cin
竟然会有一个测试用例超时,所以只好改为使用scanf
。
自定义比较函数即可,复习了strcpy
和strcmp
,如果判断输入的操作时候可以用strcmp(ops, "push") == 0
代替。
#include <bits/stdc++.h>
using namespace std;
struct Node
{
char name[25];
int val;
Node(char str[], int ele): val(ele)
{
strcpy(name, str);
}
bool operator<(const Node & obj) const
{
return val < obj.val;
}
};
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n; scanf("%d", &n);
char ops[7];
char tmpName[25];
int tmpVal;
priority_queue<Node> pq;
while (n--) {
scanf("%s", ops);
if (ops[1] == 'u') { //push operation
scanf("%s %d", tmpName, &tmpVal);
pq.push(Node(tmpName, tmpVal));
}
else {
if (pq.empty()) printf("%s\n", "none");
else {
Node tmp = pq.top();
printf("%s %d\n", tmp.name, tmp.val);
pq.pop();
}
}
}
return 0;
}