ABC023 D.射撃王

問題

風船がN個あり、それぞれ現在、高さH[i]にある。
各風船は秒速S[i]で上昇しており、1秒おきに1つずつ撃ち落とすことができる。
風船の高さを最小になるように撃ち落とした場合、風船が上がる最小の高さを返す。

N<=10^5
1<=H[i],S[i]<=10^9

考え方

高さを決め打ちし、二分探索する。

下限は0としておいて、上限は「H[i]+S[i]*Nで最大のもの」なので、その間で条件を満たせる高さを見つける。
風船が高さx以下ですべて撃ち落とせるか？という条件判定は、風船iが待てる秒数は(x-H[i])/S[i]なので、これを昇順ソートし、順番に0,1,2,3,...よりも小さくならないか？を判定すればよい。ので、判定はO(NlogN)でできる。