POJ 2010 Moo University - Financial Aid（优先队列，贪心，中位数）

#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<cstdio>
#include<set>
#include<vector>
#define MAXN 100005
#define MOD 1000000
#define ft first
#define sd second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; 
int n,c,f;
pii a[MAXN];
ll lm[MAXN],rm[MAXN];//维护每个数对儿左边n/2个最小花费和，和右边n/2个最小花费和
priority_queue<ll> pq;//大顶堆
int main(){
    while(~scanf("%d%d%d",&n,&c,&f)){
        while(!pq.empty())
            pq.pop();
        for(int i=0;i<c;i++){
            scanf("%d%d",&a[i].ft,&a[i].sd);//f为分数，s为奖学金 
            lm[i]=0;rm[i]=0;
        }
        sort(a,a+c);//先按分数升序排序，分数相同按奖学金升序排序
        int tot=n/2;
        for(int i=0;i<=c-1-n/2;i++){//维护左边的
            if(i<n/2){//所有学员中前n/2个 
                pq.push(a[i].sd);
                lm[tot]+=a[i].sd;//第n/2+1个数左边的最小花费合 
            }else{
                ll no=lm[tot];
                if(a[i].sd>=pq.top())//如果没法更新花费。那么就让其和上面的相同 
                    lm[++tot]=no;
                else{//有更小的花费值
                    pq.push(a[i].sd);
                    lm[++tot]=no-pq.top()+a[i].sd;
                    pq.pop();
                }
            }
        }
        while(!pq.empty())
            pq.pop();
        tot=c-1-n/2;
        for(int i=c-1;i>=n/2;i--){//维护右边的
            if(i>c-1-n/2){//所有学员中后n/2个 
                pq.push(a[i].sd);
                rm[tot]+=a[i].sd;
            }else{
                ll no=rm[tot];
                if(a[i].sd>=pq.top())//如果没法更新花费。那么就让其和上面的相同 
                    rm[--tot]=no;
                else {//有更小的花费值
                    pq.push(a[i].sd);
                    rm[--tot]=no-pq.top()+a[i].sd;
                    pq.pop();
                }
            }
        }
        int id=-1;
        for(int i=c-1-n/2;i>=n/2;i--){//从后往前找最大合法中位数
            ll now=a[i].sd+lm[i]+rm[i];
            if(now<=f){
                id=a[i].ft;
                break;
            }
        }
        printf("%d\n",id);
    }
    return 0;
}