AtCoder Beginner Contest 312 C - Invisible Hand

AtCoderをやり始めた。 全然問題が解けないので、復習する。

atcoder.jp

問題

りんご市場に$N$人の売り手と ${M}$人の買い手がいます。 $i$番目の売り手は、$A_i$円以上でならりんごを売ってもよいと考えています。 $i$番目の買い手は、$B_i$円以下でならりんごを買ってもよいと考えています。

次の条件を満たすような最小の整数 $X$を求めてください。

条件：りんごを$X$円で売ってもよいと考える売り手の人数が、りんごを$X$円で買ってもよいと考える買い手の人数以上である。

制約

• $1$ $\leq$ $N$, ${M}$ $\leq$ $2$ $\times$ 10⁵
• $1$ $\leq$ $A_i$, $B_i$ $\leq$ 10⁹
• $ 入力される数値はすべて整数 $

私的考察

1. 売り手と買い手の金額をソートする。
2. 売り手を基準に買い手を見つける。
3. 売り手の数 $\leq$ 買い手の数となれば、OKだろう。。。

みたいにすればOKだと思い込み実装。

結果： まったく違う。

解き方

りんごを$X$円で売ってもよいと考える売り手の人数が、りんごを$X$円で買ってもよいと考える買い手の人数以上になる最小の整数 $X$を求める必要がある。

つまり。。。

1. 売り手と買い手の金額をソートする。
2. 0 ~ 10⁹ の金額間で、売り手の数 $\leq$ 買い手の数となる最小値を見つける。 （なお、探索は二分探索で行う）

みたいにすればOK。

GO言語には、sort.Search()と呼ばれる「二分探索を使用して、$f(i)$が true である[0,n)の最小インデックスを返す」関数がある。

この関数を使って、二分探索する金額に対して、$X$円で売ってもよいと考える売り手の人数と$X$円で買ってもよいと考える買い手を見つける。

以下のようになる。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func scanInt() int {
    sc.Scan()
    i, _ := strconv.Atoi(sc.Text())
    return i
}

func scanString() string {
    sc.Scan()
    return sc.Text()
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)

    N, M := scanInt(), scanInt()

    A := make([]int, N)
    for i := 0; i < N; i++ {
        A[i] = scanInt()
    }

    B := make([]int, M)
    for i := 0; i < M; i++ {
        B[i] = scanInt()
    }

    sort.Ints(A)
    sort.Ints(B)

    start := 0
    end := int(1e9) + 1 /* 10^9 + 1*/
    for {
        v := (start + end) / 2
        sell := sort.Search(N, func(i int) bool { return A[i] > v })
        buy := M - sort.Search(M, func(i int) bool { return B[i] >= v })


        if start == end {
            break
        }

        if sell < buy {
            start = v + 1
        } else if buy <= sell {
            end = v
        }
    }
    fmt.Println(start)
}