TopCoder SRM 601, Division 2, Level 1 : WinterAndMandarins

概要

　いくつかのバッグがあり、i 番のバッグには bags[ i ] 個の品物が入っている。このバッグから K 個選んで、K 人で分配したい。できるだけ公平に分配するため、選んだバッグの内最も多くの品物が入っているバッグと、最も少ない品物が入っているバッグの中身の数の差を最小化したい。最適な選び方をしたときの中身の数の差を求めよ。

解法

　選ぶバッグの内、中身の数が最小となるものを決めたとします。このとき、残りのバッグはそれ以上の数の品物が入っているバッグになりますが、できるだけ中身の少ないものから選んだ方が、最も多くの品物が入っているバッグの中身の数は少なくなります。従って、bags を昇順ソートして番号を振り直したとすると、i 番のバッグを最小のものとした場合、最大のものは i + K - 1 番のバッグになります。
　最小を決めたときの最大のバッグが分かったので、最小のバッグをどれにするかを全て試し、最小の差を求めればよいです。

コード

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

class WinterAndMandarins
{
public:
	int getNumber( vector <int> bags, int K )
	{
		const int N = bags.size();
		
		sort( ALL( bags ) );

		int res = INT_MAX / 2;
		REP( i, 0, N - K + 1 )
		{
			res = min( res, bags[ i + K - 1 ] - bags[i] );
		}
		return res;
	}
};