2384.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2384 on 2006-10-14 at 12:08:10 */
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 102400;
 
class Cow {
public:
	int s, m;
	void make() { scanf("%d %d", &s, &m); }
	bool operator <(const Cow& c) const { return s < c.s; }
};
 
int main()
{
	priority_queue< int > Q;
	int lsum[N], rsum[N], cn, nn, m;
	Cow c[N];
	
	while(scanf("%d %d %d", &nn, &cn, &m) != EOF) {
		for(int i = 0; i < cn; i++) c[i].make();
		sort(c, c+cn); nn /= 2;
		while(!Q.empty()) Q.pop();
		for(int i = 0, sum = 0; i < cn; i++) {
			if(Q.size() < nn) lsum[i] = m+1;
			else if(Q.size() > nn) { sum -= Q.top(); Q.pop(); lsum[i] = sum; }
			else lsum[i] = sum;
			Q.push(c[i].m); sum += c[i].m;
		}
		while(!Q.empty()) Q.pop();
		for(int i = cn-1, sum = 0; i >= 0; i--) {
			if(Q.size() < nn) rsum[i] = m+1;
			else if(Q.size() > nn) { sum -= Q.top(); Q.pop(); rsum[i] = sum; }
			else rsum[i] = sum;
			Q.push(c[i].m); sum += c[i].m;
		}
		int k = -1;
		for(int i = cn-1; i >= 0; i--)
			if(lsum[i]+rsum[i]+c[i].m <= m) { k = i; break; }
		if(k == -1) printf("-1\n");
		else printf("%d\n", c[k].s);
	}
	
	return 0;
}