悬赏关注
查看原帖
悬赏关注
793612
Miku_QwQ楼主2023/7/26 21:10

谷测满分,在另外一个OJ上WA了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct Node{
	long long score,money;
}a[200010];
bool operator <(const Node &x,const Node &y){
	return x.score<y.score;
}
int m,n;
long long minnl[200010],minnr[200010],fee;
int main(){
	scanf("%d %d %lld",&m,&n,&fee);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&a[i].score,&a[i].money);
	}
	sort(a+1,a+1+n);
	priority_queue<long long> L,R;
  //处理前缀
	for(int i=1;i<=(m-1)/2;i++){
		L.push(a[i].money);
		minnl[(m-1)/2]+=a[i].money;
	}
	for(int i=(m-1)/2+1;i<=n;i++){
		minnl[i]=minnl[i-1];
		if(!L.empty()  &&  a[i].money<L.top()){
			minnl[i]-=L.top();
			L.pop();
			minnl[i]+=a[i].money;
			L.push(a[i].money);
		}
	}
   //处理后缀
	for(int i=n;i>=n-(m-1)/2+1;i--){
		R.push(a[i].money);
		minnr[n-(m-1)/2+1]+=a[i].money;
	}
	for(int i=n-(m-1)/2;i>=1;i--){
		minnr[i]=minnr[i+1];
		if(!R.empty()  &&  a[i].money<R.top()){
			minnr[i]-=R.top();
			R.pop();
			minnr[i]+=a[i].money;
			R.push(a[i].money);
		}
	}
   //找答案
	for(int i=n-(m-1)/2;i>=(m-1)/2+1;i--){
		if(minnl[i-1]+minnr[i+1]+a[i].money<=fee){
			printf("%lld",a[i].score);
			return 0;
		}
	}
	printf("-1");
	return 0;
}

哪位大佬帮忙看一下谢谢qwq

2023/7/26 21:10
加载中...