2013 TCO Algorithm - Round 1B, Level 2 : EllysPairs

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12450

概要

偶数個の整数が与えられる。
二個ずつペアにしてそれぞれの和をとり、それらの最小値と最大値の差を最小化したときのその値はいくらか。

解法

最大値には最小値をくっ付けると和の最小値との差が小さくなります。
以下問題サイズが小さくなって同様に続くので、ソートして両端からペアにしていきます。

コード

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

class EllysPairs
{
public:
	int getDifference( vector <int> knowledge )
	{
		const int N = knowledge.size();
		sort( ALL( knowledge ) );
		
		int min = INT_MAX, max = 0;

		REP( i, 0, knowledge.size() / 2 )
		{
			min = std::min( min, knowledge[i] + knowledge[ N - 1 - i ] );
			max = std::max( max, knowledge[i] + knowledge[ N - 1 - i ] );
		}

		return max - min;
	}
};