Codeforces #178, B : Shaass and Bookshelf

問題文

http://codeforces.com/contest/294/problem/B

概要

N 冊の本があり、それぞれについて厚さ（ 1 or 2 ）と幅の情報が与えられる。
何冊かの本は立てて、残りの本は立てた本の上に寝かす（問題文中の図を参照）。
ただし、寝かした本の幅の合計が立てた本の厚さの合計を超えてはならない。
条件を満たすように本を置いたときの、立てた本の厚さの合計の最小値を求めよ。

解法

まず厚さが一種類の場合を考えます。
この場合、本を一冊上に寝かすことは、合計厚さを一単位減らして上のスペースをその本の幅だけ消費することになります。
消費される上のスペースは少ない方が良いので、寝かすべき本は幅の短い順に Greedy に決められます。

次に、厚さが二種類の場合です。
単一の厚さの本の集合について、寝かすべき本の数が決まるとその内訳は Greedy に決定されることが既に示されています。
寝かす本の内訳が決まれば、その数だけ寝かした結果の、立てた本の合計厚さと寝かした本の合計幅が計算できます。
それぞれの厚さについて、寝かす本の数を全探索し、幅と厚さの条件を満たすもののうちで最小の厚さとなるものが答えです。

コード

typedef vector<int> VI;

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

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI book1, book2;
	int thick = 0;
	REP( i, 0, n )
	{
		int t, w;
		cin >> t >> w;
		thick += t;
		( t == 1 ? book1 : book2 ).PB( w );
	}

	sort( ALL( book1 ) );
	sort( ALL( book2 ) );

	int res = INT_MAX;
	REP( num1, 0, book1.size() + 1 )
	{
		REP( num2, 0, book2.size() + 1 	)
		{
			int w1 = accumulate( book1.begin(), book1.begin() + num1, 0 );
			int w2 = accumulate( book2.begin(), book2.begin() + num2, 0 );
			int t = thick - num1 - num2 * 2;

			if ( w1 + w2 <= t )
			{
				res = min( res, t );
			}
		}
	}

	cout << res << endl;

	return 0;
}