用大根堆维护排队患者，C++ priority_queue 直接 push / top / pop，每次操作 O(log n)，共 O(n log n)。
OJ: roj
题目 ID: 1371
难度:普及-
标签:堆优先队列python
创建: 2026-09-30 07:29
更新: 2026-10-05 12:23
题目描述
医院按病情优先级安排看病。依次处理 push a b 表示姓名 a、优先级 b 的患者加入排队；pop 表示取出当前排队中优先级最大的患者，输出其姓名和优先级，若无人排队输出 none。所有优先级互不相同。
| 输入样例 | 输出样例 |
|---|---|
pop / push bob 3 / push tom 5 / push ella 1 / pop / push zkw 4 / pop |
none / tom 5 / zkw 4 |
数据范围：
思路
只有「插入」和「取最大」两种操作，这是优先队列的标志性场景：用大根堆 priority_queue<pair<ll, string> > 维护排队患者，push 入堆，pop 时取堆顶，堆空输出 none。每次堆操作
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:33
# update_at: 2026-09-30 07:33
import sys
from heapq import heappush, heappop
def solve() -> None:
"""用大根堆维护排队患者：pop 输出优先级最大者，空队输出 none。"""
data = iter(sys.stdin.read().split())
out: list[str] = []
heap: list[tuple[int, str]] = [] # 存 (-优先级, 姓名)：Python 只有最小堆，优先级取负即变大根堆
for _ in range(int(next(data))):
op = next(data)
if op == "push":
name, priority = next(data), int(next(data))
heappush(heap, (-priority, name)) # 优先级互不相同，元组比较不会走到姓名
elif heap:
neg_priority, name = heappop(heap)
out.append(f"{name} {-neg_priority}")
else:
out.append("none")
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 12:23
* update_at: 2026-10-05 12:23
*/
#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
// 大根堆：堆顶是当前排队中优先级最大的患者（pair 先比优先级，再比姓名）
priority_queue< pair<ll, string> > q;
int main() {
ll n;
scanf("%lld", &n);
for (ll i = 1; i <= n; i++) {
string op;
cin >> op;
if (op == "push") {
string name;
ll pri;
cin >> name >> pri;
q.push(make_pair(pri, name)); // 入队
} else {
// pop：输出当前优先级最大的患者
if (q.empty()) {
printf("none\n");
} else {
cout << q.top().second << " " << q.top().first << endl;
q.pop();
}
}
}
return 0;
}