注意,在用贪心的时候优先队列弹出元素之前一定要判断有没有元素可以弹出,如果没有直接跳过弹出元素环节。代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int w,v;
} a[300005];
int w[300005];
priority_queue<int>q;
int cmp(node a,node b) {
return a.w<b.w;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k;
cin>>n>>k;
for(int i = 1; i<=n; i++) {
cin>>a[i].w>>a[i].v;
}
for(int i = 1; i<=k; i++) {
cin>>w[i];
}
sort(a+1,a+n+1,cmp);
sort(w+1,w+k+1);
int ans;
ans = 0;
int i,j;
for(i = 1,j = 1; i<=n && j<=k; i++) {
while(j<=k && a[i].w>w[j]) {
if(!q.empty()) {
ans = ans+q.top();
q.pop();
}
j++;
}
q.push(a[i].v);
}
while(!q.empty() && j<=k){
ans = ans+q.top();
q.pop();
j++;
}
cout<<ans<<"\n";
return 0;
}