题目大意：这只Bessie真是太顽皮了，她又搞了个学校，准备招生，准备通过一个考试筛选考生，但是不能招到每个学生，每个学生也不能一定能上学，要资助，问你在一定资金内，怎么收学生，使收到的学生的平均分最高？
这一道题怎么做呢？我们知道，题目给了一个条件就是N一定是奇数，这样其实就给了我们一个套路，那就是N一定是中间的那个数，一开始我想着用一个堆去从头到尾查找，结果想了很久还是失败了。
其实这一道题要用到两个堆，分别储存左翼和右翼，我们想得到N在中间的时候左翼和右翼加起来在资金的时候的所有值，而且N必须要大（先把score排序就可以了）
这一题说实话我没想出来，不过也是给自己一个教训吧，原来堆还可以这样用。
参考：http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid.html
#include <iostream>
#include <functional>
#include <algorithm>
#include <queue>
#define MAX_N 2000000001 using namespace std; typedef int Position;
typedef int Heap;
typedef struct _set
{
int score;
int aid;
bool operator <(const _set &x)const
{
return score < x.score;//最大堆
}
}Cows;
int fcmop(const void *a, const void*b)
{
return (*(Cows *)b).score - (*(Cows *)a).score;
} static Cows cows_set[];
static Heap Heap_Cow[];
static int Left[];
static int Right[]; void Insert(Position, const int);
int DeleteMax(int *const);
void Get_Left(const int, const int);
void Get_Right(const int, const int); void Insert(Position pos, const int item)
{
Position s = pos, pr;
for (; s > ; s = pr)
{
pr = s % == ? (s - ) >> : s >> ;
if (Heap_Cow[pr] < item)
Heap_Cow[s] = Heap_Cow[pr];
else break;
}
Heap_Cow[s] = item;
} int DeleteMax(int *const Heap_size)
{
int max_item = Heap_Cow[], tmp = Heap_Cow[(*Heap_size)--];
Position s, s1, s2, pr = ; for (; pr <= *Heap_size;)
{
s1 = pr << ; s2 = s1 + ;
if (s2 <= *Heap_size)
{
s = Heap_Cow[s1] > Heap_Cow[s2] ? s1 : s2;
Heap_Cow[pr] = Heap_Cow[s];
pr = s;
}
else if (s1 <= *Heap_size)
{
Heap_Cow[pr] = Heap_Cow[s1];
pr = s1;
break;
}
else break;
}
Insert(pr, tmp);
return max_item;
} void Get_Left(const int N, const int C)
{
int mid = N / , sum_tmp = , i, Heap_size = ; for (i = ; i < mid; i++)//初始化
{
Left[i] = MAX_N;
sum_tmp += cows_set[i].aid;
Insert(++Heap_size, cows_set[i].aid);
}
for (; i < C; i++)
{
Left[i] = sum_tmp;
Insert(++Heap_size, cows_set[i].aid);
sum_tmp += cows_set[i].aid;
sum_tmp -= DeleteMax(&Heap_size);//减去最大值
}
} void Get_Right(const int N, const int C)
{
int mid = N / , sum_tmp = , i, Heap_size = ; for (i = C - ; i >= C - mid; i--)//初始化
{
Right[i] = MAX_N;
sum_tmp += cows_set[i].aid;
Insert(++Heap_size, cows_set[i].aid);
}
for (; i >= ; i--)
{
Right[i] = sum_tmp;
Insert(++Heap_size, cows_set[i].aid);
sum_tmp += cows_set[i].aid;
sum_tmp -= DeleteMax(&Heap_size);//减去最大值
}
} int main(void)
{
int N, C, F, i;
Cows tmp;
while (~scanf("%d%d%d", &N, &C, &F))
{
for (i = ; i < C; i++)
{
scanf("%d%d", &tmp.score, &tmp.aid);
cows_set[i] = tmp;
}
qsort(cows_set, C, sizeof(Cows), fcmop);
Get_Left(N, C);
Get_Right(N, C); for (i = ; i < C; i++)
{
if (Left[i] + Right[i] + cows_set[i].aid <= F)
{
printf("%d\n", cows_set[i].score);
break;
}
}
if (i == C) printf("-1\n");
}
return ;
}