- 闫晟淏 的博客
暑假七月DAY1
- @ 2025-7-15 19:44:48
错题:
C
错因:
想的程序过于复杂,最后来不及写了。下次想得简单一点
思路:
循环每次寻找有报酬的且报酬最高的工作,然后加入ans(每个工只加一次),最后再输出ans。
参考代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q1;//da
priority_queue<int,vector<int>,greater<int>> q2;//xiao
vector<pair<int,int>> jobs;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int ai,bi;
cin>>ai>>bi;
jobs.push_back({ai,bi});
}
sort(jobs.begin(),jobs.end());
int idx=0,ans=0;
for(int day=1;day<=m;day++){
while(idx<n&&jobs[idx].first<=day){
q1.push(jobs[idx].second);
idx++;
}
if(q1.size()!=0){
ans+=q1.top();//取出堆顶
q1.pop();//删除堆顶
}
}
cout<<ans<<endl;
return 0;
}
THE END