AtCoder BC102 C: Linear Approximation

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

解法

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

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

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

これが最小になるのは、数列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