問題概要
整数の集合があり,その要素は配列 により与えられる.この集合に対し,ある 1 つの要素を選んでその値を 1 増やすまたは 1 減らす操作を任意回数できる.
整数 が与えられる.少なくとも 個の連続する整数が集合に含まれるようにするために,必要な操作回数は最小で何回か?
解法
のとき,1 つの整数は連続する 個の整数と見做せるため,操作の必要はありません.この場合は 0 を return しておくとして, の場合について考えます.
まずは,ある 2 つの整数 をとったとき, が連続する整数になる(⇔)となるようにするための操作回数について考えてみます.この場合, 回の操作で目標を達成できます. から 1 つの要素を選んでそれを として固定したと考えると, の選び方として最適なものは, より大きい要素の内最小のものを とする選び方です.これは,予め を昇順ソートしておくことで簡単に求めることができます.すなわち,ソート後の配列を として,各 について を計算した内の最小値が答えとなります.
コード
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() #define SZ( v ) ( (int)( v ).size() ) class TheConsecutiveIntegersDivTwo { public: int find( vector <int> numbers, int k ) { const int N = SZ( numbers ); if ( k == 1 ) { return 0; } sort( ALL( numbers ) ); int res = LIM<>::max(); REP( i, 0, N - 1 ) { res = min( res, numbers[ i + 1 ] - numbers[i] - 1 ); } return res; } };