【競プロ典型90問】「007 - CP Classes（★3）」解法

2022年2月10日 2022年4月5日

TheLogicalBear

Free-PhotosによるPixabayからの画像

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

007 - CP Classes（★3）

ポイント

クラスを昇順ソートして、二分探索で生徒が入るべきクラスを探ります。

コード

def main():
    import sys
    from bisect import bisect_left
    sys.setrecursionlimit(10 ** 9)
    input = sys.stdin.readline

    N = int(input())
    classes = list(map(int, input().split()))
    Q = int(input())

    classes.sort()
    for _ in range(Q):
        b = int(input())
        l = bisect_left(classes, b)  # bの値に一番近いインデックスを探す
        if l == len(classes):  # インデックスが一番右端の場合は最後のクラスに入れる
            print(abs(classes[l - 1] - b))
        else:  # インデックスが右端でなければ左右のクラスで比較する
            print(min(abs(classes[l - 1] - b), abs(classes[l] - b)))


if __name__ == '__main__':
    main()

この記事を書いた人

TheLogicalBear