专题三（花式STL）

题解花式STL

[题目][A]
Moo University - Financial Aid
题目大意：

解题思路：

    解法一：先满足条件<f，找到一组最可能满足条件的牛，然后把这些牛按成绩分为两组。成绩较低的一组，用要求aid最大优先队列维护，成绩高的一组用成绩最低优先队列维护，第二组的TOP元素即为中位数。然后遍历剩下的c-n头牛，用分数大于中位数，要求aid加入后(第一组的队首或者第二组的队首中较大者出队后)sum又小于f，将第二组队首出队，push进第一组，把该头牛push进第二组；然后把第一组的队首pop
    解法二：将牛按成绩降序排列，判断中位数为哪个时，符合calf[i].aid+calf[i].left+calf[i].right<f故要求出第i头牛，左边选出half头牛，花费最少的钱，和右边选出half头牛花费最少的钱。用默认优先队列（降序）来维护aid，让aid最大的出列（当新进入的牛的aid小于队首元素）左右都一样，最后让中位数遍历。

AC代码：
解法一：

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <algorithm>
#include <cstdlib>
//解法一：先满足条件<f，找到一组最可能满足条件的牛，然后把这些牛按成绩分为两组
//成绩较低的一组，用要求aid最大优先队列维护，成绩高的一组用成绩最低优先队列维护，第二组的TOP元素即为中位数。
//然后遍历剩下的c-n头牛，用分数大于中位数，要求aid加入后(第一组的队首或者第二组的队首中较大者出队后)sum又小于f
//将第二组队首出队，push进第一组，把该头牛push进第二组；然后把第一组的队首pop
#define ll long long
#define pq priority_queue
using namespace std;
const ll maxn = 1e5+5;
typedef struct moo{
    int score,aid;
}model;
model calf[maxn];
struct cmp1{
    bool operator() (model a,model b){
        return a.aid < b.aid;
    }
};
struct cmp2{
    bool operator() (model a,model b){
        if(a.score == b.score) return a.aid < b.aid;
        else return a.score > b.score;
    }
};
bool cmp3(model a,model b){
    if(a.aid == b.aid) return a.score > b.score;
    else return a.aid < b.aid;
}
bool cmp4(model a,model b){
    return a.score < b.score;
}
int main(){
    //freopen("in.txt","r",stdin);
    ll n,c,f;
    ll i;
    ll half,ans,sum;
    model t1,t2,temp;
    priority_queue<model,vector<model>,cmp1> maxp;
    priority_queue<model,vector<model>,cmp2> minp;
    scanf("%lld%lld%lld",&n,&c,&f);
    for(i = 0;i < c;i++){
        scanf("%lld%lld",&calf[i].score,&calf[i].aid);
    }
    sort(calf,calf+c,cmp3);
    sort(calf,calf+n,cmp4);
    half = n/2;
    sum = 0;
    for(i = 0;i < half;i++){
        maxp.push(calf[i]);
        sum += calf[i].aid;
    }
    for(;i < n;i++){
        minp.push(calf[i]);
        sum += calf[i].aid;
    }
    temp = minp.top();
    ans = temp.score;
    if(sum <= f){
        for(; i < c; i++){
            if(n > 1){
                t1 = maxp.top();
                t2 = minp.top();
                if(calf[i].score > ans && sum - max(t1.aid,t2.aid) + calf[i].aid <= f){
                    minp.pop();
                    minp.push(calf[i]);
                    maxp.push(t2);
                    temp = maxp.top();
                    maxp.pop();
                    t2 = minp.top();
                    ans = t2.score;
                    sum = sum - temp.aid + calf[i].aid;
                }
            }
            else{
                if(calf[i].score > ans && calf[i].aid <= f){
                    ans = calf[i].score;
                }
            }
        }
        printf("%lld\n",ans);
    }
    else printf("-1\n");
    return 0;
}

解法二：

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <cstdlib>
#include <algorithm>
//将牛按成绩降序排列，判断中位数为哪个时，符合calf[i].aid+calf[i].left+calf[i].right < f
//故要求出第i头牛，左边选出half头牛，花费最少的钱，和右边选出half头牛花费最少的钱。
//用默认优先队列（降序）来维护aid，让aid最大的出列（当新进入的牛的aid小于队首元素）
//左右都一样，最后让中位数遍历。
#define ll long long
#define pq priority_queue
using namespace std;
const ll maxn = 1e5+5;
typedef struct moo{
    int score;
    ll aid;
    ll left;
    ll right;
}model;
model calf[maxn];
bool cmp(model a,model b){
    if(a.score == b.score) return a.aid < b.aid;
    else return a.score > b.score;
}
pq<int> q1,q2;
int main(){
    //freopen("in.txt","r",stdin);
    int n,c;
    int half;
    ll f;
    int i;
    ll sum;
    scanf("%d%d%lld",&n,&c,&f);
    for(i = 0;i < c;i++){
        scanf("%d%lld",&calf[i].score,&calf[i].aid);
        calf[i].left = 0;
        calf[i].right = 0;
    }
    sort(calf,calf+c,cmp);
    half=n/2;
    if(n > 1)
    {
        sum = 0;
        for(i = 0; i < half; i++)
        {
            q1.push(calf[i].aid);
            sum += calf[i].aid;
        }
        calf[half].left = sum;
        for(i = half+1; i < c-half; i++)
        {
            if(q1.top() > calf[i-1].aid)
            {
                sum = sum-q1.top()+calf[i-1].aid;
                q1.pop();
                q1.push(calf[i-1].aid);
            }
            calf[i].left = sum;
        }
        sum = 0;
        for(i = c-1; i > c-half-1; i--)
        {
            q2.push(calf[i].aid);
            sum += calf[i].aid;
        }
        calf[c-half-1].right = sum;
        for(i = c-half-2; i >= half; i--)
        {
            if(q2.top() > calf[i+1].aid)
            {
                sum = sum-q2.top()+calf[i+1].aid;
                q2.pop();
                q2.push(calf[i+1].aid);
            }
            calf[i].right = sum;
        }
    }
    for(i = half;i <= c-half-1;i++){
        if(calf[i].aid+calf[i].left+calf[i].right <= f){
            printf("%d\n",calf[i].score);
            break;
        }
    }
    if(i > c-half-1) printf("-1\n");
    return 0;
}