POJ 2010 Moo University Financial Aid(贪心+优先队列)

Description

学校要选出N个人发放助学金，

但有C个人申请（给出C个人的成绩和各自的申请金额），

而且学校只能发放不超过F的金钱，

找出一种策略，使得被发放助学金的学生的群体，

他们的成绩的中位数最大

贪心

按成绩排序作为基本顺序

处理上部：

选取后 N/2 个学生，将每个申请金额置于一个优先级队列中(由大到小)，并记下总和

从第 C - N / 2 - 1 个位置当做中位数依次往下测试(保证了选取最大的)

处理下部：

在基本顺序的基础上将下部分(要测试的位置以下)按申请金额由小到大排序

取前 N / 2 个的金额总和，记下最后一个位置(即 int last_pos = N / 2 - 1)

检测：

上部金额 + 下部金额 + 当前检测位置金额 <= F 即退出

否则：

①将当前检测位置 idx 并入上部

②让其前一位置 idx - 1 脱离下部

在对idx - 1这个位置检测

Code

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int score, money;
};

node stu_s[100005];///整体按成绩排序
node stu_m[100005];///下部分按钱排序

bool cmp_score(node a, node b)
{
    if(a.score != b.score)
        return a.score < b.score;
    else
        return a.money < b.money;
}

bool cmp_money(node a, node b)
{
    return a.money < b.money;
}

int main()
{
    int N, C, F;
    scanf("%d%d%d", &N, &C, &F);
    for(int i = 0; i < C; ++i)
    {
        scanf("%d%d", &stu_s[i].score, &stu_s[i].money);
        stu_m[i].score = stu_s[i].score;
        stu_m[i].money = stu_s[i].money;
    }
    sort(stu_s, stu_s + C, cmp_score);

    long long up_money = 0;
    priority_queue<int> up_half_money;
    for(int i = C - 1, cnt = 0; cnt < (N >> 1); --i, ++cnt)
    {
        up_half_money.push(stu_s[i].money);
        up_money += stu_s[i].money;
    }

    for(int i = 0; i < C; ++i)
    {
        stu_m[i].score = stu_s[i].score;
        stu_m[i].money = stu_s[i].money;
    }
    sort(stu_m, stu_m + C - N / 2 - 1, cmp_money);

    long long down_money = 0;
    int last_score = stu_m[ (N >> 1) - 1 ].score, pos = N / 2 - 1;
    for(int i = 0; i < (N >> 1); ++i)
        down_money += stu_m[i].money;

    int idx = C - 1 - N / 2;
    while(idx >= 0)
    {
        if(up_money + down_money + stu_s[idx].money <= F)
            break;

        ///中位数并入上部
        if(stu_s[idx].money < up_half_money.top())
        {
            up_money -= up_half_money.top();
            up_half_money.pop();

            up_half_money.push(stu_s[idx].money);
            up_money += stu_s[idx].money;
        }
        else
            up_half_money.push(stu_s[idx].money);

        ///中位数下一个数脱离下部
        if(stu_s[idx - 1].score < last_score)
        {
            down_money -= stu_s[idx - 1].money;
            down_money += stu_m[++pos].money;
        }
        else;
        idx --;
    }
    if(idx < 0)
        cout << "-1" << '\n';
    else
        cout << stu_s[idx].score << '\n';
    return 0;
}