Atcoder典型90問 007(★3)[二分探索]

007 - CP Classes（★3）

■要約

　問題文通り考えるとQ人の生徒について，N個のクラスを考えないといけないのでO(NQ) = 10^10でだめなことが分かる．そこで今自分が使えるアルゴリズムを考えると，bit全探索/二分探索/累積和ぐらいであり，これらが使えないか考えた．すると，今回の問題は，全部の差を考えるんじゃなくて，生徒Bのレーティングが，クラスのレーティング配列Aのどの値に近ければわかればいいので，配列Aをソートして，何番目にbのレーティングが含まれればいいか分かれば，その左右の絶対知を計算するだけという前回のABCのC問題と全く同じ解き方であることが分かった．典型90問の強さ典型たる所以を感じた瞬間であった．

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
for _ in range(Q):
 B.append(int(input()))
 
A.sort() #①ソート
import bisect
for b in B:
 ans = 10**10+1
 i = bisect.bisect_left(A, b) #②配列Aのどこの位置に挿入されるか
 #③左と右の値との不満度を計算
 if 0 <= i - 1 < N:
   a1 = A[i-1] #左側
   ans = min(ans, abs(b - a1))
 if 0 <= i < N:
   a2 = A[i] #右側
   ans = min(ans, abs(b - a2))
   
 print(ans)