【AtCoder-Ruby】ABC102 C - Linear Approximation

問題

問題文

すぬけ君は、長さ N の整数列 A を持っています。
すぬけ君は、整数 b を自由に選びます。
この時、 Ai と b + i が離れているとすぬけ君は悲しいです。
より具体的には、すぬけ君の悲しさの値は、次の式で計算されます。
なおここで、 abs(x) は x の絶対値を返す関数です。

• abs(A1 − (b +1)) + abs (A2 − (b + 2)) + ... + abs (AN − (b + N))

すぬけ君の悲しさの値の最小値を求めてください。

制約

• 1 ≤ N ≤ 2 * 10**5
• 1 ≤ Ai ≤ 10**9
• 入力はすべて整数である。

問題リンク

考えたこと

最適な b を求める。配列の位置を引いた値の一番大きいやつ？ではないな。
20分ほど考えて答えを確認

ここで、b を Bi の中央値にするのが最適であることがわかります。
中央値でない場合は、中央値に近づけることで損をしないことからこれはわかります。

ARC100 / ABC102 解説

さらっと中央値と書いてある。
配列の位置を引いた値をソートして真ん中の数。

回答

N = gets.strip.to_i
a = gets.strip.split.each_with_index.map { |c, i| c.to_i - i - 1 }.sort

b = a[N / 2]
puts a.inject(0) { |sum, n| sum + (n - b).abs }

考察

今回はコードで数え上げの処理を inject に置き換えてみた。
いつもはこんな感じ

sum = 0
N.times { |i| sum += (a[i] - b).abs }
puts sum

# 今回
# puts a.inject(0) { |sum, n| sum + (n - b).abs }