看病（信息学奥赛一本通- P1371）

有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。

第一行输入n，表示有n个操作。

对于每个操作，首先输入push或pop。

push的情况，之后会输入ai 和 bi，分别表示患者姓名和患者病情优先级。

pop后面没有输入，但需要你输出。

对于pop的操作，输出此时还在排队人中，优先级最大的患者姓名和优先级。

表示他可以进去看病了。

如果此时没人在排队，那么输出”none”，具体可见样例。

【数据规模和约定】

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)。

• 优化方案：

  1. 选择将endl替换为'\n'。（不替换也能过信息学奥赛一本同所有测试点，但是较慢）

  2. 加入 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; }