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
",maxscore);
}
return 0;
}