题解 P4952 【[USACO 2004 Mar]Financial Aid 赞助学费】

· · 题解

这显然是一道关于中位数的水题。

那么简化问题及为：

要求选出的N头牛的成绩的中位数尽可能大，我们可以考虑依次讨论每头奶牛的成绩是否适合作为中位数。

1.先把牛们的分数由小到大排序

那么这个中位数显然在[n/2+1.....c-n/2]中。

2.若k位于这个范围[n/2+1...c-n/2]，那么Score[k]是否是一个合理的中位数呢？

在[1...k-1]间定要选出n/2头牛，我们希望选总学费尽量少n/2头奶牛，设该学费总额为Left[k]（left[k]表示在k这头牛左边满足n/2头牛的钱的最小的总和，right同理)

在[k+1...c]间定也要选出n/2头牛，我们也希望选总学费尽量少n/2头奶牛，设该学费总额为Right[k]

如果满足left[k]+right[k]+money[k]<=F

那么这就是一种合理的情况

最终找出满足条件 Left[k]+Right[k]+Money[k]<=F 的最大的一个k，它对应的Score[k]即为答案。

3.求[n/2+1...c-n/2]中每个数对应的left[ ]和right[ ]

建立一个大根堆，把最左边的n/2头牛所要的费用存到堆里面，用sum记下总和。 设当前讨论到了第k头牛

if(money[k]<堆顶元素)就用money[k]把堆顶元素换掉

继续讨论下一头牛

right[ ]的求法同left[ ]!

AC代码

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
struct node{int fen,money,left,right;}cow[100005];
int C,N,F;
priority_queue<int>q;
bool cmp(node a,node b){return a.fen==b.fen?a.money<b.money:a.fen<b.fen;}
void init(){
    scanf("%d%d%d",&N,&C,&F);
    for(int i=1;i<=C;i++)scanf("%d%d",&cow[i].fen,&cow[i].money);
    sort(cow+1,cow+1+C,cmp); //先要排序
}
void LEFT(){//左边
    int sum=0;
    for(int i=1;i<=N/2;i++){
        q.push(cow[i].money);
        sum+=cow[i].money;
    }//最左边的
    for(int i=N/2+1;i<=C-N/2;i++){
        int t=q.top();
        cow[i].left=sum;
        if(cow[i].money<t){
            q.pop();
            sum=sum-t+cow[i].money;
            q.push(cow[i].money);
        }
    }
    while(!q.empty())q.pop();
}
void RIGHT(){//右边
    int sum=0;
    for(int i=C;i>=C-N/2+1;i--){
        q.push(cow[i].money);
        sum+=cow[i].money;
    }//最右边的
    for(int i=C-N/2;i>=N/2+1;i--){
        int t=q.top();
        cow[i].right=sum;
        if(cow[i].money<t){
            q.pop();
            sum=sum-t+cow[i].money;
            q.push(cow[i].money);
        }//互换
    }
}
int main(){
    int ans=-1;//赋值为-1
    init();
    LEFT();
    RIGHT();
    for(int i=C-N/2;i>=N/2+1;i--){
        if(cow[i].left+cow[i].right+cow[i].money<=F){
            ans=cow[i].fen;
            break;
        }
    }
    printf("%d",ans);
}