Heap:Moo University - Financial Aid(POJ 2010)

　　　　　　　　　　　　

　　　　　　　　　　　　　　    牛的学校

　　题目大意：这只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[100001];
static Heap Heap_Cow[100001];
static int Left[100001];
static int Right[100001];

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 > 1; s = pr)
    {
        pr = s % 2 == 1 ? (s - 1) >> 1 : s >> 1;
        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[1], tmp = Heap_Cow[(*Heap_size)--];
    Position s, s1, s2, pr = 1;

    for (; pr <= *Heap_size;)
    {
        s1 = pr << 1; s2 = s1 + 1;
        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 / 2, sum_tmp = 0, i, Heap_size = 0;

    for (i = 0; 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 / 2, sum_tmp = 0, i, Heap_size = 0;

    for (i = C - 1; i >= C - mid; i--)//初始化
    {
        Right[i] = MAX_N;
        sum_tmp += cows_set[i].aid;
        Insert(++Heap_size, cows_set[i].aid);
    }
    for (; i >= 0; 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 = 0; 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 = 0; 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 0;
}