Codeforces #219, Division 1, A ( Division 2, C ) : Counting Kangaroos is Fun

問題文

http://codeforces.com/contest/372/problem/A

概要

　n 匹のカンガルーがいて、i 番のカンガルーの大きさは である。二匹のカンガルー i, j について、 であれば、i は j のポケットに入ることができる。ポケットに入ったカンガルーは他のカンガルーを自身のポケットに入れることはできない。また、ポケットには高々一匹のカンガルーしか入れない。
　ポケットに入ったカンガルーは外からは見えなくなる。外から見えるカンガルーの数を最小化するポケットへの入り方をしたとき、何匹のカンガルーが見えるか求めよ。

解法

　a 匹のカンガルーをポケットに入れることができるとすると、a 匹の内訳は小さい方から a 匹抜き出すのが最適となります。a 匹の内で最も小さいカンガルーをポケットに入れるカンガルーは、可能なものの内で最も小さい個体を選択するのが、その後得になるので最適です。
　ポケットに入るカンガルーの数を決めたときの割り当て方が分かったので、この a を探索すれば解くことができますが、割り当てられるか試すのに かかるので、全体で になって全部試すことはできません。ところで、b 匹をポケットに入れることができるとすれば b - 1 匹もポケットに入れることができて、できないならば b + 1 匹もポケットに入れることはできません。つまり、a に関して単調性をもつので二分探索を用いることができます。これならば全体で なので間に合います。

コード

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()

bool ok( const VI &as, const int p )
{
	const int N = as.size();

	int j = p;
	REP( i, 0, p )
	{
		while ( j < N && as[i] * 2 > as[j] ) j++;
		if ( N <= j )
		{
			return false;
		}
		j++;
	}
	return true;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}
	sort( ALL( as ) );

	int lb = 0, ub = n - 1;
	while ( lb + 1 < ub )
	{
		const int mid = ( lb + ub ) / 2;
		( ok( as, mid ) ? lb : ub ) = mid;
	}

	cout << n - lb << endl;

	return 0;
}