[UVa] 10154 - Weights and Measures

題目網址: http://goo.gl/eP8tL5

題意:
(from luckycat) 


解法: (1) 可用DP，(2)  https://www.ptt.cc/bbs/Prob_Solve/M.1271995568.A.15C.html 。

Tag: STL

注意:

程式碼:

	/**
	* Tittle: 10154 - Weights and Measures
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/14
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 6000
	class Turtle {
	public:
	int w, s;
	Turtle( int _w=0, int _s=0 ): w(_w), s(_s) {}
	const bool operator<( const Turtle &op ) const {
	return s < op.s;
	}
	};
	typedef priority_queue<int> PQI;
	// declarations
	Turtle tt[N];
	int n;
	int allw;
	// functions
	// main function
	int main( void )
	{
	// input
	n = 0;
	while( scanf( "%d%d", &tt[n].w, &tt[n].s )==2 ) ++n;
	// solve
	sort( tt, tt+n );
	allw = 0;
	PQI pq;
	FOR( i, 0, n-1 ) {
	allw += tt[i].w;
	pq.push( tt[i].w );
	if( allw > tt[i].s ) {
	allw -= pq.top();
	pq.pop();
	}
	}
	// output
	printf( "%d\n", pq.size() );
	return 0;
	}

view raw 10154 - Weights and Measures.cpp hosted with ❤ by GitHub