题目大意
猪仙发现人类可以上很多大学，而猪们却没有大学可上。为了解决这个问题，于是他创立了一所大学，取名为猪仙大学。
为了选拔合适的学生入学，他发明了一种学术能力测试（简称(CSAT)），这种测试的分数异常精确，每头猪的成绩可以用1到2,000,000,000之间的一个整数表示。
猪仙大学的学费很贵（猪仙比较黑），很多猪都负担不起，他们需要申请一些奖学金((1=<奖学金<=10,000)）。可是政府并没有为猪准备奖学金，于是所有的预算都必须要从学校自身有限的基金中间扣除（设基金总额为F,(0=<F<=2,000,000,000)）。
更槽的事，猪仙大学的只有N((1=<N<=19,999))间教室，N是一个奇数，而一共有C头猪申请入学，为了让最多的猪接受教育，猪仙打算接受N头猪的申请，而且她还想让这些猪
成绩的中位数尽可能地高。
给定每头猪的(CSAT)成绩和打算申请的奖学金数目，以及可以资助的基金总数，确定猪仙接受哪些猪的申请才可以使成绩的中位数达到最大。
输入格式
- 第一行：三个用空格分开的整数：N,C 和F。
- 第二行到C+1行：每行有两个用空格分开的整数。第一个数是这头猪的 (CSAT)成绩，第二个数是这头猪想申请的奖学金。
输出格式
第一行：一个整数，表示猪仙可以得到的最大中位数，如果现有基金不够资助N头猪，则输出-1。
样例
样例输入
3 5 70
30 25
50 21
20 20
5 18
35 30
样例输出
35
算法分析
- 数据范围高达100，000 显然至少需要一个O(n(log_n))的算法
- 已经知道要招入n只猪 因此中位数i满足 (frac n2)+1≤i≤C−(frac n2)
- 如果i=(frac n2)+1 那么成绩前(frac n2) 只猪都要选上
- 因此可以枚举中位数，用一个大根堆维护奖金，枚举一个中位数如果当前的奖金比之前的大根堆堆顶小,则交换，始终保持大根堆有(frac n2)个元素，同时用f[i]来维护如果用i做中位数，前(frac n2)个数的最小奖金
- 同样，再倒序枚举一次，用g[i]表示如果用i做中位数，后(frac n2)个数的最小奖金
- 这样我们再遍历一次i 然后求出最小的f[i]+g[i]+a[i].w 对应的最大的a[i].s就是我们要的答案了
算法展示
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,c,F,ans;
int f[maxn],g[maxn],sum;
priority_queue <int> q;//大根堆
struct node{
int s,w;//s为成绩 w为奖金
}a[maxn];
int cmp(node a,node b){return a.s < b.s;}
int main(){
scanf("%d%d%d",&n,&c,&F);
for(int i = 1;i <= c;++i)scanf("%d%d",&a[i].s,&a[i].w);
sort(a+1,a+1+c,cmp);//按成绩升序排列
for(int i = 1;i <= n/2;++i){
sum += a[i].w;//计算成绩最低的前n/2个数的奖金和
q.push(a[i].w);//进堆
}
for(int i = n/2+1;i <= c;++i){
f[i] = sum;//以i为中位数 前n/2个数的最小奖金数
int top = q.top();
if(top > a[i].w){//如果当前元素的奖金数小于堆顶
q.pop();
sum -= top;
sum += a[i].w;
q.push(a[i].w);//替换掉堆顶并更新下个f[i]的值
}
}
sum = 0;
while(!q.empty()) q.pop();
for(int i = c;i >= c-n/2+1;--i){//同上
sum += a[i].w;//计算成绩最高的前n/2个数的奖金和
q.push(a[i].w);//进堆
}
for(int i = c-n/2;i >= 1;--i){
g[i] = sum;//以i为中位数后n/2个数的最小奖金数
int top = q.top();
if(top > a[i].w){//如果当前元素的奖金数小于堆顶
q.pop();
sum -= top;
sum += a[i].w;
q.push(a[i].w);//替换掉堆顶元素并更新下个g[i]的值
}
}
for(int i = c-n/2;i >= n/2+1;--i)//倒序遍历中位数以便直接输出最大的中位数
if(a[i].w + f[i] + g[i] <= F){//如果总奖金数小于限制
printf("%d",a[i].s);
return 0;
}
printf("-1
");//遍历过每一个中位数了
return 0;
}