【题目大意】
给出C头奶牛的SAT成绩和申请奖学金，选出N头牛，使得总奖学金在≤F的情况下奶牛SAT成绩的中位数最大。
【思路】
假设before[i]表示前i头奶牛中n/2头奶牛奖学金总额的最小值，而after[i]表示后i头奶牛中n/2头奶牛奖学金总额的最小值。
将C头奶牛按照SAT成绩进行排序后，从第c-n/2头开始到第n/2+1头奶牛进行枚举，如果当前before[i]+after[i]+当前奶牛申请的奖学金≤F，则退出，当前奶牛SAT成绩就是中位数的最大值。那么如何求before和after呢？可以用优先队列进行预处理。
以before为例，每新加入一头奶牛，就把它申请的奖学金累加到sum中去。如果当前优先队列的size大于n/2，则让队首（即申请奖学金最多的那一个）出队。这样，sum的总和始终未前i头奶牛中，n/2头奶牛奖学金总和的最小值。after同理从后往前做即可。
【错误点】
不要忘记了有可能是无解的，要输出-1；其次由于数组下标是0开始的，注意循环是[c-1-n/2,n/2]。
看discuss区有人说有多组数据，不写while会出错。
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXC=+;
struct node
{
int csat,req;
bool operator < (const node &x) const
{
return csat<x.csat;
}
}cow[MAXC];
int n,c,f; int before[MAXC],after[MAXC]; void pretreatment()
{
priority_queue<int> be,af;
int sum=;
for (int i=;i<c;i++)
{
be.push(cow[i].req);
sum+=cow[i].req;
if (be.size()>n/)
{
sum-=be.top();
be.pop();
}
if (be.size()<n/) before[i]=;
else before[i]=sum;
} sum=;
for (int i=c-;i>=;i--)
{
af.push(cow[i].req);
sum+=cow[i].req;
if (af.size()>n/)
{
sum-=af.top();
af.pop();
}
if (af.size()<n/) after[i]=;
else after[i]=sum;
}
} void getans()
{
int i,boolf=;
for (i=c--n/;i>=n/;i--)
{
if (before[i-]+after[i+]+cow[i].req<=f)
{
boolf=;
break;
}
}
if (boolf==)
cout<<cow[i].csat<<endl;
else cout<<-<<endl;
} int main()
{
while (scanf("%d%d%d",&n,&c,&f)!=EOF)
{
for (int i=;i<c;i++) scanf("%d%d",&cow[i].csat,&cow[i].req);
sort(cow,cow+c); pretreatment();
getans();
}
return ;
}