奖学金
题目描述
小张学院有 \(c\) 名学生，第 \(i\) 名学生的成绩为 \(ai\) ，要获得的奖学金金额为 \(bi\) 。
要从这 \(c\) 名学生中挑出 \(n\) 名学生发奖学金。这个神秘人物爱好奇特，他希望得到奖学金的同学的成绩的中位数尽可能大，但同时，他们的奖学金总额不能超过 \(f\) 。
输入格式
第一行有三个整数，分别表示要挑出的学生人数 \(n\) ，学生总人数 \(c\) 和奖学金总额的最大值 \(f\) 。
第 \(2\) 到第 \((c+1)\) 行，每行两个整数，第 \((i+1)\) 行的整数依次表示第 \(i\) 名学生的成绩 \(ai\) 和如果要给他发奖学金，则需要发的金额数 \(bi\) 。
输出格式
输出一行一个整数表示答案。如果无法满足神秘人的条件，请输出 \(−1\) 。
输入输出样例
输入 #1
3 5 70
30 25
50 21
20 20
5 18
35 30
输出 #1
35
输入 #2
5 6 9
4 0
4 1
6 3
8 0
10 4
10 5
输出 #2
6
说明/提示
样例 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;
}
代码是教练员的，自己码风有一..恶心