TopCoder, SRM 624, Division 2, Level 2 : BuildingHeightsEasy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13215&rd=15857

問題概要

　正整数の列 heights と、正整数 M ( ) が与えられる。
　heights の各要素に対し、値を 1 増やす操作を任意回できるとき、heights の内 M 個以上を等しくするために必要な操作回数の最小値を求めよ。

解法

　|heights| を N と書きます。
　まず、最終的に作られる M 個の値の候補は O( N ) 個です。もし heights に含まれない値を M 個作ったとすると、その M 個の初期状態の内で最も大きい値もまた作ることができて、そのコストは heights に含まれない値を作る場合より小さくなります。従って、最終的に作られる M 個の等しい値は、heights に初期状態で含まれる値のいずれかです。
　さて、最終的に作られる値 t を仮定したとき、t 以下の値から M - 1 個を選択して、t と等しくしなければなりません。このとき、操作の対象にする要素はどのように選択するのがよいでしょうか？　ある h ( h ∈ heights ) を t にするには、t - h のコストがかかります。t にすることが可能な要素の内、より大きいものから選択するのことで、最終的なコストを小さくできます。このことは、heights を昇順にソートしたとき、ある t を決めたときに操作の対象になる要素は連続した区間内に存在することを意味します。従って、heights[ i ] を t とした場合、開区間 ( i - M + 1, i ) 内の各 j について heights[ i ] - heights[ j ] の総和をとれば、仮定した t に対する最小コストが求まります。あとは、M 個の要素を等しくできる各 i ( M 番目以降を目標値として仮定すればよいので、M - 1 以上の i ) について最小コストを計算して、その内の最小値を return することで解くことができます。

コード

template < typename T = int > using LIM = numeric_limits<T>;

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

class BuildingHeightsEasy
{
public:
	int minimum( int M, vector <int> heights )
	{
		const int N = heights.size();

		sort( ALL( heights ) );

		int res = LIM<>::max();
		REP( i, M - 1, N )
		{
			int cost = 0;
			REP( j, i - M + 1, i + 1 )
			{
				cost += heights[i] - heights[j];
			}
			res = min( res, cost );
		}
		return res;
	}
};