Assigning to Classes - #618 div2 b

#math

要素は sort してるものとする

グループを2つに分ける
1 : 2k + 1 人がいて, 中央値は $a_i$
2 : 2l + 1 人がいて, 中央値は $a_j$
i < j としておく

$a_i \leq a_n$ を示す

i の上に k 人いる
また, i < j より, i の上にさらに l + 1 人はいる

k + l + 1 = n
(2k + 1 + 2l + 1 = 2n $\Rightarrow$ k + l = n - 1)
i の上に n 人はいる
ゆえに, $a_i \leq a_n$

$a_j \geq a_{n + 1}$ を示す

j の下に l 人いる
i < j より, j の下にさらに k + 1 人はいる

k + l + 1 = n
j の下に n 人以上いる
ゆえに, $a_j \geq a_{n + 1}$

以上より, $a_i \leq a_n, a_j \geq a_{n + 1}$
$a_j - a_i \geq a_{n + 1} - a_n$

差を小さくしたい
この下限は実現可能
交互に要素をとってったらいい

まとめ
中央値は, とれる範囲が限られる
2つの中央値を考える
それぞれ, どの範囲か調べる
差を小さくしたい
上の中央値はどこまで下げられるか
下の中央値はどこまで上げられるか