競プロ典型90問：007 - CP Classes（★3）

問題

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

挑戦結果

• 結果：解けた
• 時間：10分ぐらい

考えたこと

• 愚直はTLEする
• $A$はソートすれば二分探索で近いクラスを見つけられる。見つけたら前後のどちらか($A_i$と$A_{i+1}$)が最も近いクラスなので、それの近い方のクラスに入れればOK。

公式解説

https://twitter.com/e869120/status/1379565222541680644

解説を読んだふりかえり

• スルッと解けたので、特になし。

ソース

import bisect
# インプット
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [int(input()) for _ in range(Q)]
# 二分探索(bisect)用にソートしておく
A.sort()
INF = float('inf')
for bval in B:
    diff = INF
    # A[aidx] <= bval < A[aidx+1] を二分探索で探すので、近い方を選択採用すればOK
    aidx = bisect.bisect_left(A, bval)-1
    diff = abs(A[aidx] - bval)
    if aidx+1 < len(A):
        diff = min(diff, abs(A[aidx+1] - bval))
    print(diff)