📝

ABC231 C - Counting 2を理解し忘れないようにする

2024/09/25に公開

https://atcoder.jp/contests/abc231/tasks/abc231_c

問題概要

N人の生徒がいて身長はAi、j = 1~QまででAixj以上なのは何人になるのかを答える。

方針1 ライブラリを用いた2分探索

lower_boundでxjAi以上かそうでないかの境界値が求められるのでこれを利用する。
Aのサイズ - xjがAi未満の人数、これを出力すれば答えが求められる。
計算量はO(QlogN)

回答コード

https://atcoder.jp/contests/abc231/submissions/58087038
回答コードは配列のindexを考慮している。

Discussion