POJ-2010 Moo University - Financial Aid 题解

题目大意

总共有c个人，每个人有自己的成绩和所需要的钱，你只有f块钱，需要招n个人，你需要使这n个人的成绩的中位数尽可能的大，求出最大的中位数。

解题思路

题目要求是中位数。

那么我只需要枚举中位数，使他左右两边的花费最小。

题目的提示使用优先队列，所以我刚开始觉得是用优先队列来维护一个最小值。

发现被这个提示误导了。。

其实并不是用这个优先队列来维护。

是应该用优先队列预处理完每一位左边和右边的花费最小值。

（其实也算是用优先队列来维护，但是思路错了。。

最后只需要枚举判断即可。

完整代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 5;
struct ty {
	ll sc, f;
};
struct cmp2 {
	bool operator()(ty a, ty b) {
		return a.f < b.f;
	}
};
ty num[N];
priority_queue<ty, vector<ty>, cmp2> q1, q2;
ll minl[N], minr[N];

int cmp1(ty a, ty b) {
	return a.sc < b.sc;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n, c, f; cin >> n >> c >> f;
	ll suml = 0, sumr = 0;
	for (int i = 1; i <= c; i++) {
		cin >> num[i].sc >> num[i].f;
	}
	sort(num + 1, num + 1 + c, cmp1);
	for (int i = 1; i <= n / 2; i++)	suml += num[i].f, q1.push(num[i]);
	for (int i = c - n / 2 + 1; i <= c; i++)	sumr += num[i].f, q2.push(num[i]);
	for (int i = n / 2 + 1; i <= c - n / 2; i++) {
		minl[i] = suml;
		if (num[i].f < q1.top().f) {
			suml -= (q1.top().f - num[i].f);
			q1.pop();
			q1.push(num[i]);
		}
	}
	for (int i = c - n / 2; i > n / 2; i--) {
		minr[i] = sumr;
		if (num[i].f < q2.top().f) {
			sumr -= (q2.top().f - num[i].f);
			q2.pop();
			q2.push(num[i]);
		}
	}
	ll ans = -1;
	for (int i = c - n / 2; i > n / 2; i--) {
		ll s = minl[i] + minr[i] + num[i].f;
		if (s <= f) {
			ans = num[i].sc; break;
		}
	}
	cout << ans << endl;
}