[POJ] 2431 – Expedition - http://kuoe0.ch/1512/poj-2431-expedition/

2431 - Expedition.cpp

/*
 * =====================================================================================
 *
 *       Filename:  2431 - Expedition.cpp
 *
 *    Description:  http://poj.org/problem?id=2431
 *
 *        Version:  1.0
 *        Created:  2012/02/08 18時46分09秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  KuoE0 ([email protected])
 *   Organization:  NCKU CSIE WMMKS Lab, Taiwan
 *
 * =====================================================================================
 */
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n;
pair< int, int > stop[ 10010 ];
int P, L;
int main() {

	while ( ~scanf( "%d", &n ) ) {

		int d, c;
		priority_queue< int > PQ;
		for ( int i = 0; i < n; ++i ) {
			scanf( "%d %d", &d, &c );
			stop[ i ] = pair< int, int >( d, c );
		}
		scanf( "%d %d", &d, &c );
		for ( int i = 0; i < n; ++i )
			stop[ i ].first = d - stop[ i ].first;

		int cnt = 0, MAX = 0;
		sort( stop, stop + n );

		stop[ n ] = pair< int, int >( d, 0 );
		for ( int i = 0; i < n + 1; ++i ) {

			while ( c < stop[ i ].first && !PQ.empty() ) {
				c += PQ.top(), PQ.pop();
				++cnt;
			}

			if ( c < stop[ i ].first )
				break;
			PQ.push( stop[ i ].second );
			
		}
		if ( c < d )
			cnt = -1;
		printf( "%d\n", cnt );
	}

	return 0;
}