奖学金

题目描述

小张学院有 \(c\) 名学生，第 \(i\) 名学生的成绩为 \(ai\) ，要获得的奖学金金额为 \(bi\) 。

要从这 \(c\) 名学生中挑出 \(n\) 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的成绩的中位数尽可能大，但同时，他们的奖学金总额不能超过 \(f\) 。

输入格式

第一行有三个整数，分别表示要挑出的学生人数 \(n\) ，学生总人数 \(c\) 和奖学金总额的最大值 \(f\) 。

第 \(2\) 到第 \((c+1)\) 行，每行两个整数，第 \((i+1)\) 行的整数依次表示第 \(i\) 名学生的成绩 \(ai\) 和如果要给他发奖学金，则需要发的金额数 \(bi\) 。

输出格式

输出一行一个整数表示答案。如果无法满足神秘人的条件，请输出 \(−1\) 。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

样例 1 解释

选择成绩为 \(5\) ， \(35\) ， \(50\) 的三名同学，奖金总额为 \(18+30+21=69\)。

数据规模与约定

对于 30% 的数据，保证 n≤10^3，c≤2×10^3。

对于 100% 的数据，保证 3≤n≤10^5，n≤c≤2×10^5，0≤f≤2×10^9，0≤ai≤2×10^9,0≤bi≤10^5。

大致思路

首先要保证这道题要求中位数的最大值，那么就是尽可能的放成绩尽可能最高的那个，首先用\(sort\)根据成绩来排序，一个堆把前\(（n+1）/2\)的数放进大跟堆里，然后从\(（n+1）/2\)开始\(for\)循环来一次枚举成绩高的，要是成绩高而且奖学金需求还比大跟堆里最大的金额少，那么一定要放进去，并把价格最高的踢出来，保证刚放进去的数是第\(（n+1）/2\)个数，直到搜到第\(c-（n+1）/2\)的时候，停止，维护了当前形式的最大中位数，再从后\(（n+1）/2\)个数里向前走，求出当前形式的最小中位数，然后跑一个\(for\)循环来求出最大的中位数即可。

代码实现

#include <bits/stdc++.h>

const int maxn=2e5+5;

int n,c,F;

std::priority_queue <int> q;

struct Node{

    int s,w;//分数,奖金

} a[maxn];

bool cmp(const Node &a, const Node &b){

    return a.s<b.s;

}

int f[maxn],g[maxn],sum;;

void Init(){

    scanf("%d%d%d", &n,&c,&F);

    for(int i=1;i<=c;++i)

        scanf("%d%d", &a[i].s,&a[i].w);

    std::sort(a+1,a+1+c,cmp);//按成绩升序

}

void Solve(){

    for(int i=1;i<=n/2;++i){//成绩最低的n/2进入队列

        sum+=a[i].w;//累加总奖金

        q.push(a[i].w);//队列是维护奖金的大根堆

    }

    //f[i]:表示以i为中位数前n/2人的最小奖金

    for(int i=n/2+1;i<=c;++i){

        f[i]=sum;

        int top=q.top();

        if(top>a[i].w){//如果当前的奖金小于堆顶则交换掉

            q.pop();

            sum-=top;

            sum+=a[i].w;

            q.push(a[i].w);

        }

    }

    sum=0;

    while(!q.empty()) q.pop();

    for(int i=c;i>=c-n/2+1;--i){//成绩最高的n/2进入队列

        sum+=a[i].w;

        q.push(a[i].w);

    }

    //g[i]:表示以i为中位数后n/2人的最低奖金

    for(int i=c-n/2;i>=1;--i){

        g[i]=sum;

        int top=q.top();

        if(top>a[i].w){//交换

            q.pop();

            sum-=top;

            sum+=a[i].w;

            q.push(a[i].w);

        }

    }

    //中位数的取值范围是[n/2+1,c-n/2]

    //因为要求最大中位数，所以倒序

    for(int i=c-n/2;i>=n/2+1;--i)

        if(a[i].w+f[i]+g[i]<=F){

            printf("%d", a[i].s);

            return;

        }

    printf("-1\n");

}

int main(){

    Init();

    Solve();

    return 0;

}

代码是教练员的，自己码风有一..恶心

巴特西

TJOI2013 奖学金—大根堆实现（洛谷P3963）

奖学金