読者です 読者をやめる 読者になる 読者になる

オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。

 

問題文

abc023.contest.atcoder.jp

解法

制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。

風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、

$$T_i = (x - H_i) / S_i$$

で求められる。あとは、この時間が短い順に全ての風船を N 秒間で割っていった時に、各風船 i を Ti 秒以内に割ることができるかどうかを見てやるだけでいい。

解の取りうる最大値が大きいので一見やばそうに見えるけど二分探索は神なので余裕。

結局 $O(Nlog(max(H_i+S_i*N)))$ くらい。