Moo University - Financial Aid POJ - 2010

// Moo University - Financial Aid POJ - 2010.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://vjudge.net/problem/POJ-2010#author=GPT_zh

贝西注意到，尽管人类有许多大学可供就读，但奶牛却没有。为了解决这个问题，她和她的同伴们成立了一所新的大学，
名为“威斯康星农场大学”，简称“Moo U”。 不想录取比平均水平低的奶牛，创始人们创建了一项名为奶牛学术能力测试（CSAT）的非常精确的入学考试，
其分数范围为1到2,000,000,000。 Moo U的学费非常昂贵；并非所有小牛都能负担得起。
事实上，大多数小牛都需要某种形式的助学金（0 <= 助学金 <= 100,000）。
政府不向小牛提供奖学金，因此所有资金必须来自大学有限的基金（总金额为F，0 <= F <= 2,000,000,000）。 
更糟糕的是，Moo U只有适合奇数N（1 <= N <= 19,999）的教室，可以容纳申请的C（N <= C <= 100,000）头小牛。
贝西希望录取恰好N头小牛，以最大程度地提高教育机会。她仍希望被录取的小牛的CSAT分数中位数尽可能高。 
回想一下，奇数个整数集的中位数是排序后的中间值。例如，集合{3, 8, 9, 7, 5}的中位数是7，因为7上面恰好有两个值，下面也恰好有两个值。 
给定每头小牛的分数和所需的助学金，要接受的小牛总数，以及贝西用于助学金的总金额，确定通过谨慎录取一组最佳小牛可以获得的最大中位数分数。
输入
* 第1行：三个以空格分隔的整数N、C和F * 第2行至第C+1行：每行两个以空格分隔的整数。第一个是小牛的CSAT分数；第二个整数是小牛需要的助学金金额
输出
* 第1行：一个整数，贝西可以获得的最大中位数分数。如果没有足够的资金来录取N头小牛，则输出-1。
* 
* 

3 5 70
30 25
50 21
20 20
5 18
35 30


35



3 9 16
5 13
6 16
1 1
7 1
7 17
2 2
9 13
9 20
1 8

ans 7

Input：
5 10 10
3 3
1 7
6 1
4 10
3 1
8 3
7 10
8 1
7 7
7 9
Output：
6
Input：
5 10 10
10 1
10 3
1 2
7 6
3 3
10 2
5 5
2 4
3 2
4 10
Output:
10
Input:
5 10 10
10 6
7 1
5 3
1 1
3 3
4 6
6 4
3 1
8 5
9 5
Output:
5



1 5 10
30 25
50 21
20 20
5 18
35 10
无答案 自己看


3 5 3
4 10
5 10
6 1
7 1
8 1
无答案自己看
*/
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>


using namespace std;


const int N = 100010;
long long sumleft[N];
long long sumright[N];
int n, c;
long long f;

struct COW {
	long long score;
	int cost;
}cows[N];

//要求奖学金多的 优先 便于堆的弹出
struct cmpfunc {
	bool operator()(const struct COW& a, const struct COW& b) {
		return a.cost < b.cost;
	}
};

//分数小优先
bool cmp(const struct COW& a, const struct COW& b) {
	/*if (a.score < b.score) return true;
	else if (a.score == b.score) return a.cost > b.cost;

	return false;*/

	return a.score < b.score;
}


void solve() {
	sort(cows, cows + c,cmp);
	
	
	{
		priority_queue<struct COW, vector<struct COW>, cmpfunc> q;
		long long sum = 0; int limit = n / 2;
		for (int i = 0; i < c; i++) {
			sumleft[i] = 0x3f3f3f3f3f3f3f3f;
			int curr = i - 1;
			if (curr < 0) continue;
			if (q.size() < limit || cows[curr].cost < q.top().cost) {
				sum += cows[curr].cost;
				q.push(cows[curr]);
				if (q.size() > limit) {
					sum -= q.top().cost;
					q.pop();
				}
			}
			sumleft[i] = sum;
			if (q.size() < limit) sumleft[i] = 0x3f3f3f3f3f3f3f3f;
		}

		//while (!q.empty()) { q.pop(); } sum = 0;
	}
	priority_queue<struct COW, vector<struct COW>, cmpfunc> q;
	long long sum = 0; int limit = n / 2;
	for (int i = c - 1; i >= 0; i--) {
		sumright[i] = 0x3f3f3f3f3f3f3f3f;
		int curr = i + 1;
		if (curr == c) continue;
		if (q.size() < limit || cows[curr].cost < q.top().cost) {
			sum += cows[curr].cost;
			q.push(cows[curr]);
			if (q.size() > limit) {
				sum -= q.top().cost;
				q.pop();
			}
		}
		sumright[i] = sum;
		if (q.size() < limit) sumright[i] = 0x3f3f3f3f3f3f3f3f;
	}

	long long ans = -1;

	for (int i = 0; i < c; i++) {
		if (sumright[i] + cows[i].cost + sumleft[i] <= f) {
			ans = max(ans,cows[i].score);
		}
	}

	cout << ans << endl;
}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> c >> f;
	for (int i = 0; i < c; i++) {
		cin >> cows[i].score >> cows[i].cost;
	}

	solve();


	return 0;
}