[AtCoder] ABC 169 E – Count Median

問題

方針

自然数 \( m \) を

\[ m = \left \lfloor \dfrac{N}{2} \right \rfloor\]

とします。

\( N \) が奇数のとき

中央値の最小値は \( A \) を昇順に並べた時の \( A_{m} \) となり、最大値は \( B \) を昇順に並べた時の \( B_m \) となります。したがって、

\[ B_m – A_m + 1 \]

が答えとなります。

\( N \) が偶数のとき

中央値 \( x \) の範囲は、

\[ \dfrac{A_{m – 1} + A_{m}}{2} \leq x \leq \dfrac{B_{m – 1} + B_{m}}{2}\]

となり、\( A_{m – 1} + A_{m} \) から \( B_{m – 1} + B_{m} \) まで \( 1 \) 刻みずつ動くので、答えは、

\[B_{m – 1} + B_{m} – (A_{m – 1} + A_{m}) + 1 \]

となります。

コード