2010.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

priority_queue< int ,vector<int> > q;

typedef pair< int, int > cow;

cow c[1000000];
int money[100000];
int n, m, f;

int main()
{
	int i, v;

	scanf( "%d %d %d", &n, &m, &f );
	
	for( i=0; i<m; i++ )
		scanf( "%d %d", &c[i].first, &c[i].second );

	sort( c, c+m );

	for( v=0, i=0; i<n/2; i++ )
	{
		v += c[i].second;
		q.push( c[i].second );
	}
	money[i] += v;

	for( ; i<m-n/2-1 ; i++ )
	{
		if( q.top() > c[i].second )
		{
			v -= q.top();
			q.pop();
			v += c[i].second;
			q.push( c[i].second );
		}
		money[i+1] += v;
	}

	while(!q.empty())q.pop();
	
	for( v=0,i=m-1; i>=m-n/2; i-- )
	{
		v += c[i].second;
		q.push( c[i].second );
	}
	

	for( ; i>=n/2 ;i-- )
	{
		money[i] += v;
		if( money[i] + c[i].second <= f )break;

		if( q.top() > c[i].second )
		{
			v -= q.top();
			q.pop();
			v += c[i].second;
			q.push( c[i].second );
		}
	}

	if( i>=n/2 ) printf( "%d\n", c[i].first );
	else printf( "%d\n", -1 );

	return 0;
}