問題

C - Linear Approximation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解法
以下の数式の値を最小にする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
コメント