1 条题解
-
0
###解析: 枚举最后到最前时间;优先做期限内学分最高的作业; 先将所有作业按完成期限从大到小排序; 从后到前枚举作业时间,将时限内可以完成的作业加入优先队列,优先完成学分最高的作业;
#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
- 上传者