Dragon Arrow written by Tatsuya Nakaji, all rights reserved animated-dragon-image-0164

中央値の取り方

Apr 15, 2019


B - AtCoder Market atCoder問題


ヒント 

𝑁 個の数 𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑁 があります。 |𝑥 − 𝑎1| + |𝑥 − 𝑎2| + ⋯ + |𝑥 − 𝑎𝑁| の最小値を求めなさい。

実は、最小値となる 𝑥 は「𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑁 の中央値」となる!


wikipedia: 中央値(ちゅうおうち、英: median)とは、代表の一つで、有限個のデータを小さい順に並べたとき中央に位置する。 たとえば5人の人がいるとき、その5人の年齢の中央値は3番目に年寄りな人の年齢である。 ただし、データが偶数個の場合は、中央に近い2つのの算術平均をとる。


Ribyで中央値を求めるコード

(a.size % 2).zero? ? a[a.size/2 - 1, 2].inject(:+) / 2.0 : a[a.size/2]


解答

n = gets.to_i
a, b = n.times.map{ gets.strip.split.map(&:to_i) }.transpose
a.sort!
b.sort!
# a配列の中央値 偶数の時の中央値は真ん中二つの平均値なので注意
ent = (n%2).zero? ? (a[n/2 - 1, 2].inject(:+) / 2.0).round : a[n/2]
# b配列の中央値
exit = (n%2).zero? ? (b[n/2 - 1, 2].inject(:+) / 2.0).round : b[n/2]
count = 0
n.times do |i|
count += (ent- a[i]).abs
count += (b[i] - a[i]).abs
count += (exit - b[i]).abs
end
puts count