POJ_2010 Moo University - Financial Aid 【堆预处理】

一、题面

POJ2010

二、分析

堆预处理

首先可以考虑吧随便取一个点，判断两侧的最小的总费用是多少，然后相加判断是否满足条件。如果直接判断会超时，所以需要用大根堆预处理一下。先看从分数最小的往最大的预处理，先取N/2个相加，并把他们都加入到堆中，先假设这个和值是最大的，然后不断往后扫描的过程中，不断更新大根堆的根值，以及它的和。反向预处理类似。比较容易出错的是选的范围，如果不用那些不可能到的点，可以随意点，但如果需要使用这些点，需要用足够大的值填充。

三、AC代码

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 #include <fstream>

 #include <iostream>

 using namespace std;

 const int MAXN = 1e5+;

 int N, C, F, ans;

 struct Node

 {

     int score, aid;

     bool operator<(const Node t)const

     {

         return score < t.score;

     }

 }Calves[MAXN];

 int Left[MAXN], Right[MAXN];

 void solve()

 {

     priority_queue<int, vector<int>, less<int> > pql, pqr;

     int i, temp, sum = ;

     //正向扫描求最小和，保持大根堆的容量始终为N/2

     for(i = ; i < N/; i++)

     {

         sum += Calves[i].aid;

         Left[i] = ;

         pql.push(Calves[i].aid);

     }

     for(i; i < C-N/; i++)

     {

         Left[i] = sum;

         temp = pql.top();

         if(Calves[i].aid < temp)

         {

             pql.pop();

             sum -= temp;

             sum += Calves[i].aid;

             pql.push(Calves[i].aid);

         }

     }

     //反向扫描

     sum = ;

     for(i = C-; i > C-N/-; i--)

     {

          sum += Calves[i].aid;

          Right[i] = ;

          pqr.push(Calves[i].aid);

     }

     for(i; i >= N/; i--)

     {

         Right[i] = sum;

         temp = pqr.top();

         if(Calves[i].aid < temp)

         {

             pqr.pop();

             sum -= temp;

             sum += Calves[i].aid;

             pqr.push(Calves[i].aid);

         }

     }

 }

 int main()

 {

     // freopen("input.txt", "r", stdin);

     // freopen("out.txt", "w", stdout);

     while(scanf("%d %d %d", &N, &C, &F)!=EOF)

     {

         bool flag = false;

         for(int i = ; i < C; i++)

         {

             scanf("%d %d", &Calves[i].score, &Calves[i].aid);

         }

         sort(Calves, Calves+C);

         solve();

         for(int i = C-N/-; i >= N/; i--)

         {

             if(Right[i] + Left[i] + Calves[i].aid <= F)

             {

                 printf("%d\n", Calves[i].score);

                 flag = true;

                 break;

             }

         }

         if(!flag)

         {

             printf("-1\n");

         }

     }

     return ;

 }