警示后人
查看原帖
警示后人
678447
CSPAK_Zhangxiuqi0011楼主2024/9/1 15:03

注意,在用贪心的时候优先队列弹出元素之前一定要判断有没有元素可以弹出,如果没有直接跳过弹出元素环节。代码:

#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;
}

2024/9/1 15:03
加载中...