谷测满分,在另外一个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