【POJ - 2010】Moo University - Financial Aid(优先队列)


Moo University - Financial Aid

Descriptions

奶牛大学:奶大招生,从C头奶牛中招收N(N为奇数)头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。

Input

*第1行:三个以空格分隔的整数N,C和F 

*第2..C + 1行:每行两个以空格分隔的整数。首先是小牛的CSAT分数; 第二个整数是小牛所需的经济援助金额 

Output

*第1行:一个整数,即Bessie可以达到的最大中位数分数。如果没有足够的钱来接纳N小牛,输出-1。 

Sample Input

3 5 70
30 25
50 21
20 20
5 18
35 30

Sample Output

35

Hint

样本输出如果Bessie接受CSAT分数为5,35和50的小牛,则中位数为35.所需的总经济援助为18 + 30 + 21 = 69 <= 70。 
 
题目链接
 
先将奶牛按分数排序,考虑每个奶牛作为中位数时,比它分数低(前面的)的那群牛的学费总和lower_i,后面的总和upper_i。然后从分数高往分数低扫描,满足aid_i + lower_i + upper_i <= F的第一个解就是最优解。
 
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>1
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100005
#define P pair<int,int>
using namespace std;
P a[Maxn];
int N,C,F;
// 牛i作为中位数时,lower[i]表示分数低于它的牛的学费总和
int lower[Maxn],upper[Maxn];
int main()
{
    cin>>N>>C>>F;
    int half=N/2;
    for(int i=0; i<C; i++)
        cin>>a[i].first>>a[i].second; //分数  学费
    sort(a,a+C);
    {
        //求出lower[i]
        int total=0;
        priority_queue<int>q;
        for(int i=0; i<C; i++)
        {
            lower[i]=q.size()==half?total:INF;
            q.push(a[i].second);
            total+=a[i].second;
            if(q.size()>half)
            {
                //去掉一个学费最高的
                total-=q.top();
                q.pop();
            }
        }
    }
    {
        //求出upper[i]
        int total=0;
        priority_queue<int>q;
        for(int i=C-1; i>=0; i--)
        {
            upper[i]=q.size()==half?total:INF;
            q.push(a[i].second);
            total+=a[i].second;
            if(q.size()>half)
            {
                //去掉一个学费最高的
                total-=q.top();
                q.pop();
            }
        }
    }
    int ans=-1;
    for(int i=C-1; i>=0; i--)
        if(a[i].second+lower[i]+upper[i]<=F)
        {
            ans=a[i].first;
            break;
        }
    cout<<ans<<endl;
    return 0;
}

 


作者:Sky丨Star,发布于:2019/08/13
原文:https://www.cnblogs.com/sky-stars/p/11345104.html