Javaばば挑戦中⑦

連日の晴れ、4月並みの暖かさを感じて、ぽかぽか…

今日、Atcoder094回目を挑戦しようと思います。

まずC問題を着目します。

N個の数X₁、X₂、…、Xｎを与えて、Ｎは偶数で、i=1,2,…nに対して、X₁、X₂、…、XｎからXiのみを除いたもの、X₁、X₂、…,Xi−1,Xi+1,…Xｎの中央値を求める問題。

中央値を求める問題ですね、予備知識としては、k個数字（kは奇数）の中央値は(k+1)/2番目大きい数値であること。

よくわからないですが、具体例を見てみる、

4つの数字2,4,4,3に、それぞれの数字を除いて、その中央値は、

①2を除いて、4,4,3の中央値は2番目大きい数値4です。

②4を除いて、2,4,3の中央値は2番目大きい数値3です。

③4を除いて、2,4,3の中央値は2番目大きい数値3です。

④3を除いて、2,4,4の中央値は2番目大きい数値4です。

以上の流れを考察すると、気付いた箇所があります。Nは固定なので、一つ数字を取り除くと、結果は必ずN/2番目大きい数値、因みに取り除かれた数字はそれより小さいであれば、N/2番目大きい数値に影響を与えないので、N/2番目大きい数値は正解です、取り除かれた数字値それより大きいまたはそれと同じであれば、どうなっているのか？大きい順は一つずらされ、N/2 -1番目大きい数値は正解になりますね。