小さい方からk番目の値
億マス計算
C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder
すべてのマスを計算してからk番目の値を求めることはできない。
そもそも「小さい方からK番目の値がXである」とはどういうことか?
これは「X-1以下の数はK個未満しかないが、X以下の数はK個以上ある」ということ。別の言い方をすると「X以下の数がK個以上あるような最小のX」が小さい方からK番目の数。二分探索を使う。
「Xを決めたとき、X以下の数はK個以上あるか?」という問題を繰り返し解く。どうやって数えるか。
各行を一つずつ見ていく
i行目に含まれるK以下の数の個数は、のうち以下であるようなものの個数と一致
bをソートしておけば(再び)二分探索でO(log(N))時間で求まる。
おまけ 配列aの要素のうち、値がx以下であるものの数
int num = upper_bound(a.begin(), a.end(), x)-a.begin();