TopCoder SRM 599, Division 2, Level 1 : MiniatureDachshund

概要

体重が weight である犬がいる。
N 個の蜜柑があって、i 番の蜜柑の重さは mikan[ i ] である。
犬が一つの蜜柑を食べると、体重が蜜柑の重さ分だけ増加する。
体重 5,000 以下を保ったまま食べられる蜜柑の最大数を求めよ。

解法

同じ個数の蜜柑を食べた状態なら、残りの許容量が多い方が有利です。
従って、軽い蜜柑から食べるのが最適な順序となります。
そのような順序で食べたとき、いくつまで食べられるかをてきとーに数えれば解けます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class MiniatureDachshund
{
public:
	int maxMikan( vector <int> mikan, int weight )
	{
		const int N = mikan.size();
		sort( ALL( mikan ) );
		
		int sum = weight;
		REP( i, 0, N )
		{
			sum += mikan[i];
			if ( 5000 < sum )
			{
				return i;
			}
		}
		return N;
	}
};