1 条题解
-
0
紧急任务池 · 讲解
思路与接口
使用
priority_queue<pair<long long,int>>。C++ 的pair默认按字典序比较,大根堆先取第一项较大的 pair,第一项相同时取第二项较大的 pair。存入{priority, -id},这样 priority 越大越优先,priority 相同时 id 越小,−id 越大,也越优先。ADD调用push。TAKE先用empty()检查空池;非空时通过top()取得当前最优任务,输出其第二项的相反数,再调用pop()。pop()本身不返回被删除的元素。正确性
堆中的一个 pair 唯一表示一个尚未被取走的任务。它的字典序恰好对应题目要求的两个优先规则,所以堆顶一定是应当取出的任务。每次 ADD 增加该任务,每次 TAKE 删除堆顶,归纳可知任务池内容和全部输出均符合要求。
复杂度
每次放入或取出最多 O(log q),空池检查 O(1),总时间 O(q log q),空间 O(q)。
常见错误
- 直接存
{priority,id}到默认大根堆,在紧急程度相同时先取较大的 id;配套错误程序和大量同优先级数据覆盖此错误。 - 按加入顺序处理并列,而题目要求按 id。
- 没有先判断空池就调用
top()。 - 认为任务取走后可复用 id;输入中的唯一性是全局的。
数据验证说明
Python 在小规模上保存任务字典并线性选择
(-priority,id)最小项;最大规模上用独立heapq。随机数据特意包含大量重复 priority,并随机打乱加入的 id。原创来源记录
本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。
C++17 参考实现
#include <iostream> #include <queue> #include <string> #include <utility> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; // pair 默认先比较第一项,再比较第二项:以 -id 实现较小 id 优先。 priority_queue<pair<long long, int>> tasks; while (q--) { string op; cin >> op; if (op == "ADD") { int id; long long priority; cin >> id >> priority; tasks.push({priority, -id}); } else if (tasks.empty()) { cout << "EMPTY\n"; } else { cout << -tasks.top().second << '\n'; tasks.pop(); } } } - 直接存
- 1
信息
- ID
- 5261
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者