TopCoder SRM 608, Division 2, Level 2 : MysticAndCandiesEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12998&rd=15841

問題概要

　合計で C 個の飴があり、いくつかの箱に入っている。それぞれの箱に入っている飴の正確な数は分からないが、i 番の箱に入っている飴の数は高々 high[ i ] であることが分かっている。これらの箱の内からいくつかを選んで開け、それらには入っている飴を全て取り出す。確実に X 個以上の飴を取り出したいとき、最小でいくつの箱を開ける必要があるか求めよ。

解法

　開ける箱の集合を決めたとき、得られる飴の数が最も少なくなるケースは、開けないことにした箱に可能な限り多くの飴が入っている場合です。ここから更に、開ける箱の数が同じ選び方であれば、開けないことにする箱を high が小さい順に選んだ方が得られる飴の数が多くなることが分かります。
　開けない箱の集合を S としたとき、得られる飴の数は と求まります。開けない箱の数を全て試してこの値を計算し、X 以上となるものが解候補です。解候補の内、開ける箱の数が最小となるものが答えです。

コード

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

class MysticAndCandiesEasy
{
public:
	int minBoxes( int C, int X, vector <int> high )
	{
		const int N = high.size();

		sort( ALL( high ) );

		int res = N, sum = 0;
		REP( i, 0, N )
		{
			sum += high[i];
			if ( X <= C - sum )
			{
				res = min( res, N - 1 - i );
			}
		}
		return res;
	}
};