奖学金

奖学金

Descrption

• 猪仙发现人类可以上很多大学，而猪们却没有大学可上。为了解决这个问题，于是他创立了一所大学，取名为猪仙大学。
• 为了选拔合适的学生入学，他发明了一种学术能力测试（简称 \(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)\)头猪申请入学，为了让最多的猪接受教育，猪仙打算接受 \(N\) 头猪的申请，而且她还想让这些猪 \(CSAT\) 成绩的中位数尽可能地高。
• 所谓中位数，就是在一堆数字在排序后处在最中间的那个数字，比如 \(\{3,8,9,7,5\}\) 的中位数就是 \(7\)。
• 给定每头猪的 \(CSAT\) 成绩和打算申请的奖学金数目，以及可以资助的基金总数，确定猪仙接受哪些猪的申请才可以使成绩的中位数达到最大。

Input

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

Output

• 第一行：一个整数，表示猪仙可以得到的最大中位数，如果现有基金不够资助 \(N\) 头猪，则输出 \(-1\)。

Sample Input

3 5 70 
30 25 
50 21 
20 20 
5 18 
35 30

Sample Output

35

Hint

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

• 分析

  • 数据范围高达 \(10\) 万，显然至少是\(O(n*log(n))\) 才能通过。
  • 我们分析性质中位数 \(a_i\) 必须满足：\(\frac{n}{2}+1 \le i\le C-\frac{n}{2}\) 。
  • 当 \(i=\frac{n}{2}+1\) 时，我们必须选上最小分数最低的前 \(\frac{n}{2}\) 的猪。
  • 所以我们可以枚举每一个中位数，用一个维护奖金的大根堆，每枚举完一个中位数，如果当前的奖金比堆顶的小，则交换，始终保证堆的有 \(\frac{n}{2}\) 个数，同时用一个数组 \(f[i]\) 维护如果选 \(a_i\) 为中位数，前 \(\frac{n}{2}\) 个数的最小奖金。
  • 同上，倒序维护，求出 \(g[i]\) 表示，如果选 \(a_i\) 为中位数，则后 \(\frac{n}{2}\) 个数最小奖金。
  • 显然答案为满足 \(f[i]+g[i]+a[i].w<=F\) 的最大的 \(a[i].s\) 。

• Code

  #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;
  }
  

奖学金

原文：https://www.cnblogs.com/hbhszxyb/p/13201902.html