TopCoder SRM 608, Divisin 1, Level 1 : MysticAndCandies

問題文

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

問題概要

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

解法

　開ける箱の集合を決めたとき、得られる飴の数が最も少なくなるケースは、開けることにした箱には可能な限り少なく、開けないことにした箱に可能な限り多くの飴が入っている場合です。そのようなケースでは、次のいずれかの条件を満たします。

• 開けることにした箱には全て low 個の飴しか入っていない
• 開けることにした箱の内、一つ以上は low より大きい数の飴が入っている ⇔ 開けないことにした箱全てに high 入れても合計が C より少なく、開ける箱の中身を増やせる

　前者を満たす場合を考えると、開ける箱の数が同じであれば、low が大きい箱を優先して開けた方が得られる飴の数が多くなります。開けることにした箱の集合を S とすると、得られる飴の数は です。これが X 以上となる選び方が解候補です。
　後者を満たす場合を考えると、開けない箱の数が同じであれば、high が小さい箱を優先して開けないことにした方が得られる飴の数が多くなります。開けないことにした箱の集合を T とすると、得られる飴の数は です。これが X 以上となる選び方が解候補です。
　これら二つの観点から得られた解候補の内、最良のものが全体での答えです。

コード

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

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

		sort( ALL( low ), greater<int>() );
		sort( ALL( high ) );

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