Moo University - Financial Aid

题意：

   一个私立学校的学生要申请奖学金，而学校的金额有限。因此，学校希望在金额不超过F的情况下从C中选得N对数。

   给出三个数N,C,F。分别代表在C对数中要取得N对数。而每对数分别代表成绩，跟申请金额。要求取得N对数中的总金额不超过F的条件下，然取得中间的以为学生的成绩最高。（N为even）

算法分析：

   本题有两种解法，一种是用优先队列，一种是二分;

一、利用堆实现  

  先说堆的实现方法，我们可以现对头尾的N/2进行处理，因为头尾的N/2个数一定不可能成为中位数即答案。然后，在左右扫描记录当前的最小金额。最后，在两边夹逼得出最大中位数。

   如何处理左右扫描呢?

   我以头为例（尾的扫描也一样），先得到队列中一个最大的金额，跟当前的比较如果比当前的大，则更新之。这样队列就会始终保持这在当前成绩之前的N/2个最小的金额。尾一个道理。最后用头尾相加得到最大值。

二、二分实现

   二分的还是比较好想到的，就是对题目要求的答案进行二分。这里先对成绩排序然后二分。然而这题的二分返回值有点特殊。

  具体细节请看代码.

堆实现版：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100000 + 20;
struct Node{
   int score,aid,id;
};

int N,C,F;
Node cow_score[MAXN],cow_aid[MAXN];

bool cmp_score(const Node& a,const Node& b){
   return a.score < b.score;
}

bool cmp_aid(const Node& a,const Node& b){
   return a.aid < b.aid;
}

int main()
{
    cin >> N >> C >> F;
    for(int i = 0;i < C;++i){
       cin >> cow_score[i].score >> cow_score[i].aid;
    }
    sort(cow_score,cow_score + C,cmp_score);
    for(int i = 0;i < C;++i){
        cow_score[i].id = i;
    }
    memcpy(cow_aid,cow_score,sizeof(Node) * C);
    sort(cow_aid,cow_aid + C,cmp_aid);

    int ans = -1,lb = 0,ub = C;
    while(ub - lb > 1){
        int mid = (ub + lb) >> 1;

        int lft = 0,rht = 0,sum = cow_score[mid].aid;

        for(int i = 0;i < C;++i){
            if((cow_aid[i].id < mid)&&(sum + cow_aid[i].aid <= F)&&(lft < N / 2)){
                sum += cow_aid[i].aid;
                ++lft;
            }
            else if((cow_aid[i].id > mid)&&(sum + cow_aid[i].aid <= F)&&(rht < N / 2)){
                sum += cow_aid[i].aid;
                ++rht;
            }
        }

        if((lft < N / 2)&&(rht < N / 2)){
            ans = -1;
            break;
        }
        else if(lft < N / 2){
            lb = mid;
        }
        else if(rht < N / 2){
            ub = mid;
        }
        else{
            ans = cow_score[mid].score;
            lb = mid;
        }
    }

    cout << ans << endl;
    return 0;
}

二分实现版：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;

const int MAXN = 100000 + 10;
int N,F,C;
struct Cow_score{
     int score,aid,rval,lval;
     Cow_score():rval(0),lval(0){};
     bool operator < (const Cow_score& rhs)const{   //排序score
          return score < rhs.score;
     }
};
struct Cmp_score{          //排序aid
      bool operator()(Cow_score a,Cow_score b){
          return a.aid < b.aid;
      }
};
Cow_score cow[MAXN];

int main()
{
    while(~scanf("%d%d%d",&N,&C,&F)){
        N /= 2;
        for(int i = 0;i < C;++i){
            scanf("%d%d",&cow[i].score,&cow[i].aid);
        }
        sort(cow,cow + C);
        priority_queue<Cow_score,vector<Cow_score>,Cmp_score> left_aid;
        priority_queue<Cow_score,vector<Cow_score>,Cmp_score> right_aid;

        Cow_score tmp;
        int sumaid = 0;
        for(int i = 0;i < N;++i){
            sumaid += cow[i].aid;
            left_aid.push(cow[i]);
        }
        for(int i = N;i < C - N;++i){         // 枚举左边
            cow[i].lval = sumaid;
            tmp = left_aid.top();
            if(tmp.aid > cow[i].aid){
                left_aid.pop();
                left_aid.push(cow[i]);
                sumaid = sumaid - tmp.aid + cow[i].aid;
            }
        }
        sumaid = 0;
        for(int i = C - N;i < C;++i){
            sumaid += cow[i].aid;
            right_aid.push(cow[i]);
        }
        for(int i = C-N-1;i >= N;--i){        //枚举右边
            cow[i].rval = sumaid;
            tmp = right_aid.top();
            if(tmp.aid > cow[i].aid){
                right_aid.pop();
                right_aid.push(cow[i]);
                sumaid = sumaid - tmp.aid + cow[i].aid;
            }
        }
        int maxscore = -1;
        for(int i = N;i < C - N;++i){        //夹中间
            if(cow[i].lval + cow[i].rval + cow[i].aid <= F&&maxscore < cow[i].score){
                maxscore = cow[i].score;
            }
        }

        printf("%d\n",maxscore);
    }
    return 0;
}

poj2010 Moo University - Financial Aid