AtCoder BC102 C: Linear Approximation

問題

C - Linear Approximation

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解法

以下の数式の値を最小にするbをどのようにして求めるかという問題です。

$$
abs(A_1-(b+1)) + abs(A_2-(b+1)) + … + abs(A_N-(b+1))
$$

これは、Bi = Ai – 1 とすると

$$
abs(B_1-b) + abs(B_2-b) + … + abs(B_N-b)
$$

と書き換えることがが出来ます。

これが最小になるのは、数列Bの中央値をbとした場合です。

図にしてみるとよく分かります。
（見やすくするためにBはソート済みとしています）

Nが奇数の場合、bがB3より大きく（小さく）なるとその分合計値が増加します。

Nが偶数の場合、B2〜B3の間から外れると、その分合計値は大きくなります。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

0.upto(n-1) do |i|
    a[i] -= (i+1)
end
a.sort!

m = a[n/2]

ans = 0
0.upto(n-1) do |i|
    ans += (a[i] - m).abs
end

puts ans