1 条题解

  • 0
    @ 2026-11-16 20:48:26

    紧急任务池 · 讲解

    思路与接口

    使用 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
    上传者