1 条题解

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

    三维任务排序:讲解

    思路与 STL 接口

    使用结构体存三个字段。sort 的比较器逐字段比较:priority 不同时用 >,deadline 不同时用 <,最后 id 用 <。等价地可比较键 (−priority,deadline,id)。比较器不修改记录。

    复杂度

    时间 O(n log n),记录存储 O(n)。

    常见错误

    漏掉 id 平局规则;把降序和升序混淆;使用 >= 或 <= 会破坏严格弱序,完全相等的对象必须比较为 false。

    验证方法

    Python oracle 独立读取操作并模拟或排序,不调用标准程序。正式数据含手算样例、边界、固定种子随机和两个最大规模用例;另做 200 次小规模差分,验证器拒绝非法状态和多余 token。common_wrong.cpp 保留上述一种常见逻辑错误,正式数据必须能够拒绝它。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    struct Task{int id;long long priority,deadline;};
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<Task>a(n);for(auto&t:a)cin>>t.id>>t.priority>>t.deadline;sort(a.begin(),a.end(),[](const Task&a,const Task&b){if(a.priority!=b.priority)return a.priority>b.priority;if(a.deadline!=b.deadline)return a.deadline<b.deadline;return a.id<b.id;});for(int i=0;i<n;++i)cout<<(i?" ":"")<<a[i].id;cout<<'\n';}
    
    
    • 1

    信息

    ID
    5257
    时间
    2000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者