きままにものづくり

日々の気付いたことなんかを書いてます。

SRM582Div1Easy

問題

N人の戦士が与えられ、それぞれの戦士の強さはs[i]である。また、M種類の強さes[j]を持つec[j]匹のモンスターも与えられる。戦士は自身より強さの小さいモンスターを討伐できる。戦士は一匹のモンスターを倒すと疲労度が1増える。すべてのモンスターを討伐する時のN人の戦士の中の最大の疲労度の最小値を求めよ。すべてのモンスターを討伐できない場合は-1を返す。

解法

最大の疲労度に対して二分探索を行う。最大の疲労度を固定することで、モンスターを討伐できるかの判定が可能になる。

計算量

 O(NM log V)
N: 戦士の数
M: モンスターの種類
V: モンスターの数

コード

広告を非表示にする