概要
あるプログラミングコンテストで、自分以外の参加者は 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; } };