看病（信息学奥赛一本通- P1371）
【题目描述】
有个朋友在医院工作，想请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【提示】
【数据规模和约定】
1≤n≤100000，每个人的优先级都不一样，0≤优先级≤2000000000。
姓名都是小写字母组成的，长度小于20。
1. 解题思路
本题是典型的动态有序集合维护问题。
如果是用数组存储，每次插入或删除都需要排序或移动元素，时间复杂度是O(N)或O(N log N)，在 N很大时无法接受。
最优解是使用二叉堆，对应 C++ STL 中的 priority_queue。
数据结构：
定义结构体 people 存储姓名和等级。
排序规则 (核心)：
STL 优先队列默认是大根堆（堆顶最大）。我们需要重载 < 运算符。
这样定义后，
level越大的元素会被视为“更大”，从而浮到堆顶，满足题目“优先级高者先出”的要求。
2. 总结与问题 (TLE)
代码逻辑正确，但这道题第一次提交有一个测试点TLE了
问题所在：
在循环中频繁使用 endl。
endl 等价于 \n + fflush()（强制刷新缓冲区）。在大数据量（如10^5次操作）下，这种频繁的 I/O 刷新会导致严重的超时 (TLE)。
优化方案：
选择将
endl替换为'\n'。（不替换也能过信息学奥赛一本同所有测试点，但是较慢）加入 I/O 加速挂（必须）：
ios::sync_with_stdio(false); cin.tie(0);
这能让 C++ 的输入输出速度提升数倍，是竞赛题的标准起手式。
完整代码
#include <bits/stdc++.h> #include <queue> using namespace std; struct people{ char name[30]; long long level; //重载<运算符，按照优先级进行排序 优先级高的在前 friend bool operator <(people a,people b){ return a.level<b.level; } }; string a;//a代表操作 priority_queue<people> q; int main(){ //关键优化：关闭流同步，解除cin/cout与scanf/printf的绑定，极大提升速度 ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a;//读入操作 if(a=="pop"){//出队操作 if(!q.empty()){//如果当前队列不为空 cout<<q.top().name<<" "<<q.top().level<<endl; q.pop(); } else{//如果当前队列为空 cout<<"none"<<endl; } } else if(a=="push"){//入队操作 people tmp; cin>>tmp.name;//入队病人名字 cin>>tmp.level;//入队病人优先级 q.push(tmp); } } return 0; }