锐客网

  1. 首页 > it技术 > >

信息学C++|第三部分 数据结构 -- 第三章 树1371（看病）

1371：看病
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4289 通过数: 1132
【题目描述】
有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。
【输入】
第一行输入n，表示有n个操作。
对于每个操作，首先输入push或pop。
push的情况，之后会输入ai 和 bi，分别表示患者姓名和患者病情优先级。
pop后面没有输入，但需要你输出。
【输出】
对于pop的操作，输出此时还在排队人中，优先级最大的患者姓名和优先级。
【信息学C++|第三部分 数据结构 -- 第三章 树1371（看病）】表示他可以进去看病了。
如果此时没人在排队，那么输出”none”，具体可见样例。
【输入样例】
7
pop
push bob 3
push tom 5
push ella 1
pop
push zkw 4
pop
【输出样例】
none
tom 5
zkw 4
【提示】
【数据规模和约定】
1≤n≤100000，每个人的优先级都不一样，0≤优先级≤2000000000。
姓名都是小写字母组成的，长度小于20。
思路：本题容易超时，使用优先队列priority_queue从大到小来解决，先判断输入的是pop 还是push,因为第一个字符都是p所有判断第二个字符是o 还是u ,我们判断如果是pop 就是s[1] ='o’来区分是压入还是弹出，然后判断如果队空就输出none 不空就输出姓名和编号，否则就是压入姓名和编号。

#include using namespace std; int T; char s[10]; struct node{char name[21]; int num; //优先级} a; bool operator < (node A,node B)//重载符号“<”{return A.num < B.num; //以优先级为判断标准}priority_queue,less > q; //优先队列int main(){cin >> T; while(T--){scanf("%s",&s); if(s[1]=='o') //即pop s[0]='p',s[1]='o', push s[0]='p',s[1]='u'区分是压入还是弹出{if(q.empty()) cout<<"none"<

    推荐阅读


    上一篇：董伟娟|董伟娟 焦点网络初级5期 洛阳 坚持原创分享第1009天（2020.2.19星期三）

    下一篇：RMQ问题 及st表