1 条题解

  • 0
    @ 2024-10-29 10:31:24

    ###解析: 枚举最后到最前时间;优先做期限内学分最高的作业; 先将所有作业按完成期限从大到小排序; 从后到前枚举作业时间,将时限内可以完成的作业加入优先队列,优先完成学分最高的作业;

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    struct node{
        int q;//期限
        int f;//学分
    };
    node a[1000006];
    bool cmp(node x,node y){
        return x.q>y.q;
    }
    priority_queue <int> q;//大根堆
    long long ans=0;
    int main() {
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i].q>>a[i].f;
        }
        sort(a+1,a+n+1,cmp);//按期限从大到小排序
        int p=1;//从第一个作业开始
        for(int i=n;i>=1;i--){
            while (a[p].q>=i&&p<=n){//将期限内可以完成的作业加入优先队列
                q.push(a[p].f);
                p++;
            }
            if (!q.empty()){//优先完成学分最高的作业
                ans+=q.top();
                q.pop();
            }
        }
        cout<<ans;
        return 0;
    }

    信息

    ID
    614
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者