[鉄則B11] Binary Search 2

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cj

任意の値未満の値の個数を求める問題。

問題を要約する

• シャッフルされた配列で X 未満の値の個数は？

解き方

bsearch_index を find-minimum モードで使う。求めた「X 以上の値のインデックス」がそのまま「X 未満の値の個数」になる。

ミスりやすいところ

配列が、

A = [5, 6]

のとき、7 未満は 2 だが、

A.bsearch_index { |e| e >= 7 }  # => nil

とすると 7 以上がないため nil になってしまうので nil なら A.size に

A.bsearch_index { |e| e >= 7 } || A.size  # => 2

しないといけない。

他には無限大を置いておく方法もある。

A << Float::INFINITY
A.bsearch_index { |e| e >= 7 }  # => 2

解答 (AC)

N = gets.to_i                                           # => 5
A = gets.split.collect(&:to_i)                          # => [1, 3, 3, 3, 1]
Q = gets.to_i                                           # => 2
X = Q.times.collect { gets.to_i }                       # => [4, 3]
A.sort!                                                 # => [1, 1, 3, 3, 3]
A << Float::INFINITY                                    # => [1, 1, 3, 3, 3, Infinity]
ans = X.collect { |x| A.bsearch_index { |e| e >= x } }  # => [5, 2]
puts ans