AtCoderBeginnerContest231 C問題300点 「Counting 2」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N , Q \leq 2 \times 10^5
気持ち
制約を見ると $ N = 2\times 10^5 であるため
計算量は $ O(N \log N)ぐらい、ソートでもするのかな?という気持ちになります。
$ N人の生徒の順番は関係ないのでとりあえずソートします。(ソートしておいたほうが考察しやすいことのほうが多いので)
ソートをすると $ x_i 以上の生徒は、二分探索で求められるということがわかるため二分探索で考えます。 解法
「気持ち」の通り、二分探索をすればいいです。
具体的には、以下のようなソート済み数列$ Aが与えられたときに、二分探索で座標を求めます。
https://gyazo.com/478d0b2bf61ca63e5e764f6a9bc71b0a
数列が単調に増加している、このような単調性をもつようなものに対して二分探索はうまく効きます。 二分探索の実装は以下のめぐる式二分探索を利用するとよいです。
また、言語によっては lower_bound という、数列に対して自動で二分探索してくれるメソッドがあるため利用すると良いです。
計算量
$ O(N \log N)
新たな学び
反省点
二分探索で mid を求めるのは (ok + ng) / 2
- ではない(忘れていますね...)
コード
code: go
func main() {
io := NewIo()
defer io.Flush()
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
N, Q := io.NextInt(), io.NextInt()
A := make([]int, N)
for i := 0; i < N; i++ {
}
sort.Slice(A, func(i, j int) bool { return Ai < Aj }) for i := 0; i < Q; i++ {
x := io.NextInt()
ok := N
ng := -1
for ok-ng > 1 {
mid := (ok + ng) / 2
ok = mid
} else {
ng = mid
}
}
io.PrintLn(N - ok)
}
}