競プロ典型 90 問 007 - CP Classes 解説

準備やりました．

問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ)

QCFium 法が通ったので制約が上がりました．

解説

$A_i$ をソートして，$B_j$ の前後にある数との差の小さい方を取れば良いです． $B_j$ の $A$ の中での位置は，二分探索によって求められるので，全体の計算量は $O((N+M)\log N)$ になります．

サンプルコード

#include <iostream>
#include <algorithm>
constexpr int INF = 1000000000;
int N, Q, A[300010];
int main() {
    std::cin >> N;
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::sort(A, A + N);
    std::cin >> Q;
    for (int i = 0; i < Q; i++) {
        int B;
        std::cin >> B;
        int ans = INF;
        auto p = std::upper_bound(A, A + N, B);
        if (p != A + N) ans = std::min(ans, *p - B);
        if (p != A) ans = std::min(ans, B - *std::prev(p));
        std::cout << ans << std::endl;
    }
    return 0;
}