TopCoder SRM 603, Division 2, Level 2 : SplitIntoPairs

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12939&rd=15836

概要

　要素数が偶数である数の（多重）集合が与えられる。要素数を N として、この集合を N / 2 個のペアに分割する（一つの数は丁度一つのペアに属する）。ここで、負の整数 X が与えられ、ペアの積は X 以上になっているようにしたい。そのようなペアは最大いくつ作ることができるか？

解法

　X の制約から、負×負と非負×非負は共に valid となるので、負数の数が偶数であれば N / 2 個の valid なペアを作ることができます。そうでないとき、一つだけ負×非負のペアを作る必要があります。このとき、このペアの絶対値はできるだけ小さい方が良いので、それぞれ絶対値が最も小さいものを選ぶのが最適となります。残った数は偶数個の負数と偶数個の非負数なので、問題無く valid なペアを作ることができます。このような選び方をしたとき、それが valid なペアならば N / 2 個の valid なペアを作ることができ、そうでないならば N / 2 - 1 個しか作ることができません。

コード

typedef long long LL;
typedef vector<int> VI;

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

#define PB( n ) push_back( n )

class SplitIntoPairs
{
public:
	int makepairs( vector <int> A, int X )
	{
		const int N = A.size();

		VI nega, nature;
		FOR( a, A )
		{
			( a < 0 ? nega : nature ).PB( a );
		}
		sort( ALL( nega ), greater<int>() );
		sort( ALL( nature ) );

		return N / 2 - ( nega.size() % 2 && (LL)nega[0] * nature[0] < X );
	}
};