POJ2010: Moo University - Financial Aid

http://poj.org/problem?id=2010

蟻本でpriority_queueと二分探索のどちらでも取り上げられているように解法が2通りある。

1.
http://omochan.hatenablog.com/entry/2017/06/30/214614
この問題と同じように、真ん中を決めてしまえば独立に考えられるので前後で前処理を施す。
その際priority_queueを使えばO(NlogN)でできる。

2.
真ん中を二分探索する。適当にやってもO(N(logN)^2)で通る。

下のcodeは解法1のもの。

int N, C, F;
pi P[100010];
ll S[100010], rS[100010];

void get_sum(ll *s) {
	ll sum = 0;
	priority_queue<int> que;
	int n = (N - 1) / 2;
	for(int i = 0; i < C; i++) {
		if(que.size() < n) {
			sum += P[i].second;
			que.push(P[i].second);
		}
		else {
			if(que.top() > P[i].second) {
				sum -= que.top(); que.pop();
				sum += P[i].second; que.push(P[i].second);
			}
		}
		if(que.size() == n) s[i] = sum;
		else s[i] = INF;
	}
}

int main() {
	scanf("%d%d%d", &N, &C, &F);
	for(int i = 0; i < C; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		P[i] = make_pair(a, b);
	}
	if(N == 1) {
		int ans = -1;
		for(int i = 0; i < C; i++) {
			if(P[i].second > F) continue;
			ans = max(ans, P[i].first);
		}
		printf("%d\n", ans);
	}
	else {
		sort(P, P + C);
		get_sum(S);
		reverse(P, P + C);
		get_sum(rS);
		reverse(rS, rS + C);
		reverse(P, P + C);
		int ans = -1;
		for(int i = 1; i < C - 1; i++) {
			if(S[i - 1] + rS[i + 1] + P[i].second <= F) ans = max(ans, P[i].first);
		}
		printf("%d\n", ans);
	}
}