洛谷P3963 [TJOI2013]獎學金

堆

題目傳送門

首先這道題不可二分，自己YY一下挺顯然的。

把每個人按照成績排序，從大往小掃，用三個可删除的堆 q 1 , q 2 , q 3 ​ q1,q2,q3​ q1,q2,q3​維護。 q 1 , q 3 ​ q1,q3​ q1,q3​分别維護目前位置左右的前 k ​ k​ k​大， q 2 ​ q2​ q2​維護左邊不是前 k ​ k​ k​大的，相當于 q 1 ​ q1​ q1​的後備。

具體實作見代碼：

#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
#define F inline
using namespace std;
typedef long long LL;
struct data{ int x; LL w; }a[N];
struct Q{
	priority_queue<LL> q,d;
	F void push(LL x){ q.push(x); }
	F void erase(LL x){ d.push(x); }
	F LL top(){
		while (!d.empty()&&q.top()==d.top())
			q.pop(),d.pop(); return q.top();
	}
	F void pop(){
		while (!d.empty()&&q.top()==d.top())
			q.pop(),d.pop(); q.pop();
	}
	F LL size(){ return q.size()-d.size(); }
}q1,q2,q3;
int c,n; LL f,s1,s2;
F char readc(){
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	return l==r?EOF:*l++;
}
F int _read(){
	int x=0; char ch=readc();
	while (!isdigit(ch)) ch=readc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
	return x;
}
F bool cmp1(data a,data b){ return a.w<b.w; }
F bool cmp2(data a,data b){ return a.x<b.x; }
F int pd(){
	for (int i=1;i<n-c/2;i++){
		if (q1.size()<c/2) q1.push(a[i].w),s1+=a[i].w;
		else if (q1.top()>a[i].w)
			q2.push(-q1.top()),s1-=q1.top()-a[i].w,q1.pop(),q1.push(a[i].w);
		else q2.push(-a[i].w);
	}
	for (int i=n-c/2+1;i<=n;i++) q3.push(a[i].w),s2+=a[i].w;
	for (int i=n-c/2;i>c/2;i--){
		if (s1+s2+a[i].w<=f) return i;
		if (q3.top()>a[i].w) s2+=a[i].w-q3.top(),q3.pop(),q3.push(a[i].w);
		if (q1.top()<a[i-1].w) q2.erase(-a[i-1].w);
		else q1.erase(a[i-1].w),q1.push(-q2.top()),s1-=q2.top()+a[i-1].w,q2.pop();
	}
}
int main(){
	c=_read(),n=_read(),f=_read();
	for (int i=1;i<=n;i++) a[i].x=_read(),a[i].w=_read();
	sort(a+1,a+n+1,cmp1);
	for (LL i=1,s=0;i<=c;i++)
		if ((s+=a[i].w)>f) return puts("-1"),0;
	sort(a+1,a+n+1,cmp2);
	return printf("%d\n",a[pd()].x),0;
}