奖学金

猪仙发现人类可以上很多大学，而猪们却没有大学可上。为了解决这个问题，于是他创立了一所大学，取名为猪仙大学。
为了选拔合适的学生入学，他发明了一种学术能力测试（简称 CSAT），这种测试的分数异常精确，每头猪的成绩可以用1到2，000,000,000之间的一个整数表示。
猪仙大学的学费很贵（猪仙比较黑），很多猪都负担不起，他们需要申请一些奖学金（1<=奖学金<=10000）。可是政府并没有为猪准备奖学金，于是所有的预算都必须要从学校自身有限的基金中间扣除（设基金总额为 F,0<=F<=2,000,000,000）。
更槽的事，猪仙大学的只有 N(1<=N<=19999)间教室，N 是一个奇数，而一共有C(N<=C<=100,000)头猪申请入学，为了让最多的猪接受教育，猪仙打算接受头猪的申请，而且她还想让这些猪CSAT成绩的中位数尽可能地高。
给定每头猪的CSAT成绩和打算申请的奖学金数目，以及可以资助的基金总数，确定猪仙接受哪些猪的申请才可以使成绩的中位数达到最大。

输入格式

第一行：三个用空格分开的整数：N,C 和F 。

第二行到C+1行：每行有两个用空格分开的整数。第一个数是这头猪的CSAT成绩，第二个数是这头猪想申请的奖学金。

输出格式

第一行：一个整数，表示猪仙可以得到的最大中位数，如果现有基金不够资助 N

头猪，则输出-1 。

样例输入

3 5 70

30 25

50 21

20 20

5 18

样例输出

数据范围与提示

猪仙接受CSAT分数为5,35,50的猪的申请，中位数为35，需支付的奖学金总额为18+30+21=69<=70.

思路：

一：中位数ai的范围为n/2+1<=i<=c-n/2

二：枚举中位数，用f[i]表示中位数为ai时前n/2的最小资金和（因为此时n/2已对结果产生不了影响）并用堆维护

三：同理用g[i]表示中位数为ai时后n/2的最小资金和，用堆维护

结果是显然满足f[i]+g[i]+e[i].w的最大的成绩

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=100000+10;
 4 typedef long long ll;
 5 priority_queue<int> q;
 6 struct Node{
 7     int grade,w;
 8 }e[maxn];
 9 bool Cmp(const Node &a,const Node &b){
10      return a.grade<b.grade;
11 }
12 int main(){
13     int n,c;
14     ll r;
15     scanf("%d%d%lld",&n,&c,&r);
16     for(int i=1;i<=c;i++){
17         scanf("%d%d",&e[i].grade,&e[i].w);
18     }
19     sort(e+1,e+1+c,Cmp);
20     int f[maxn],g[maxn],sum=0;
21     for(int i=1;i<=n/2;i++){
22          sum+=e[i].w;
23          q.push(e[i].w);
24     }
25     f[n/2+1]=sum;
26     for(int i=n/2+1;i<=c-n/2-1;i++){
27          if(e[i].w<q.top()){
28               sum-=q.top();
29               q.pop();
30               sum+=e[i].w;
31               q.push(e[i].w);
32          }
33          f[i+1]=sum;
34     }
35     while(!q.empty()) q.pop();
36     sum=0;
37     for(int i=c;i>=c-n/2+1;i--){
38          q.push(e[i].w);
39          sum+=e[i].w;
40     }
41     g[c-n/2]=sum;
42     for(int i=c-n/2;i>=n/2+2;i--){
43          if(e[i].w<q.top()){
44              sum-=q.top();
45              q.pop();
46              q.push(e[i].w);
47              sum+=e[i].w;
48          }
49          g[i-1]=sum;
50     }
51     int flag=0;
52     for(int i=c-n/2;i>=n/2+1;i--){
53          if((long long)f[i]+g[i]+e[i].w<=r&&flag==0){
54              printf("%dn",e[i].grade);
55              flag=1;
56          }
57     }
58     if(flag==0) printf("-1");
59     return 0;
60 }

View Code

原文链接: https://www.cnblogs.com/HZOIDJ123/p/13210511.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360573

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

集训

奖学金