問題

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_b

考え方

差の最大値を最小化したい。これはよくある典型問題で、最小化したい値 $x$ を二分探索することで最小値を求めることができる。問題を言い換えると

「差を $x$ とするとき、 $\{A_N\}, \{B_N\}$ を用いてペアを $K$ つ以上作ることができるかどうか判定し、この $x$ の最小値を求めよ」となる。

$x$ が決まれば、貪欲法で求めることができる。 $\{A_N\}, \{B_N\}$ はソートしておく。各 $A_i$ について $A_i - x$ 以上の最小の $B_j$ とマッチングさせることが最善である。ただし $B_j \gt A_i + x$ となる場合はマッチングできない。そのようにマッチングさせていったときにペアが $K$ つ以上できるかどうか求めれば良い。