题解：P4952 [USACO04MAR] Financial Aid

· · 题解

一道贪心的题目。

我们通过样例分析就可以简化一下这道题其实就是让我们在 C 个奶牛中选出 N 个奶牛，在总花费 \le F 的情况下使得这 N 个牛的中位数最大。

分析

首先我们可以先把这 C 头奶牛按照成绩先从小到大排个序，然后看以第 i 个奶牛作为中位数时，他的最小花费是多少。怎么看呢？我们可以以 i 为分界点，i 左边选 \frac{ N }{ 2 } , i 的右边选 \frac{ N }{ 2 }，在中位数一定的情况下在左边那部分中选花费最小的 \frac{ N }{ 2 } 个奶牛，用数组 L_{ i } 来存储，同理，右边的 R_{i} 也是这么的，然后我们从大到小讨论两边的花费加起来在加上中位数 i 的和如果是小于 F 的话那么第一个满足条件的就是我们的答案。

具体实现

我们可以用一个大根堆，里面存当前的奶牛，如果出现了更优的奶牛，我们就可以把队首那个最差的奶牛踢出去，把更优的奶牛放入大根堆。举个例子，假设现在堆里有 10 和 8 两头奶牛，接着来了一头 7 的奶牛，那么我们就可以把当前在堆顶的 10 踢出去，把更优的 7 放进来，假设又来了个 11 此时， 11 不够优那么就不能放入，最后答案就是 L_{i} + R_{i} + a_{ i }.money。

AC 代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
int n,c,f,ans=-1; 
struct node{
    int cast,money;
}a[100010];
int l[100010],r[100010];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inline void write(int x) {
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
bool cmp(node a,node b){
    return a.cast<b.cast;
}
int main(){
    n=read(),c=read(),f=read();
    for(int i=1;i<=c;i++){
        a[i].cast=read(),a[i].money=read();
    }
    sort(a+1,a+1+c,cmp);
    priority_queue<int>q;
    int sum1=0,sum2=0;
    int i;
    for(i=1;i<=n/2;i++){//先将前n/2入堆
        q.push(a[i].money);
        sum1+=a[i].money;//当前的总和
    }
    for(i=n/2+1;i<=c-n/2;i++){
        l[i]=sum1;          
        if(q.top()>a[i].money){//如果当前的比堆顶更优就进行替换
            sum1-=q.top();
            sum1+=a[i].money;           
            q.pop();
            q.push(a[i].money);
        }
    } 
    priority_queue<int>p;//同理求R[i]
    for(i=c;i>=c-n/2+1;i--){
        p.push(a[i].money);
        sum2+=a[i].money;
    }
    for(i=c-n/2;i>=n/2+1;i--){
        r[i]=sum2;  
        if(p.top()>a[i].money){
            sum2=sum2-p.top()+a[i].money;           
            p.pop();
            p.push(a[i].money);
        }       
    }
    for(i=c-n/2;i>=n/2+1;i--){
        if(l[i]+r[i]+a[i].money<=f){
            printf("%d",a[i].cast); 
            return 0;
        }
    }
    write(-1);
    return 0;
}