2013 TCO Algorithm - Round 1C, Level 2 : TheOlympiadInInformatics

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12456&rd=15585

概要

あるプログラミングコンテストで、自分以外の参加者は N 個の部屋に別れて参加している。
各部屋に何人の参加者がいるかは分からないが、各部屋の参加者の合計得点は分かる。
自分よりも得点が高くなる人数を k 以下にしたいとき、自分は最低何点とればよいか求めよ。

概要

得点の範囲が広いので総当りはできません。
ところで、得点→人数の関数を考えると、これは単調性を持ちます。
従って、二分探索が可能なので間に合わせることができます。

コード

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

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TheOlympiadInInformatics
{
public:
	int find( vector <int> sums, int k )
	{
		LL lb = -1, ub = sums.size() * 100000000000LL;

		while ( 1 < ub - lb )
		{
			LL mid = ( lb + ub ) / 2;
		
			if ( check( sums, k, mid ) )
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}

		return ub;
	}

	bool check( VI sums, LL k, LL point )
	{
		LL res = 0;
		REP( i, 0, sums.size() )
		{
			res += sums[i] / ( point + 1 );
		}
		return res <= k;
	}
};