競プロ典型90問-007

問題:

https://atcoder.jp/contests/typical90/tasks/typical90_g

解説:

kyopro_educational_90/007.jpg at main · E869120/kyopro_educational_90 · GitHub

 

愚直に計算するとO(300,000 ^ 2)で到底間に合わないので二分探索を用いる必要がある。

C++のライブラリには、lower_bound()なる便利なものがあるらしい。

 

 

方針としては、

①Aをソートする

②Bの各要素に対し、B[i] <= A[j] となる最小のjを探す(ここでlower_bound()を用いる)

⓷解の候補は j or j-1 (j=0の時に注意)