ABC102<難問>

ABC102C

この問題は手がつけられなかった。
AtCorder問題

自分の発想

for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = a[i] - (i + 1);
        }

要素全部を取得して、i + 1 番目なので i + 1 を引く。
その後、ある定数 b を引いて絶対値を取る。
ある定数bはb[i]の平均を取るなど考えた。

公式解説

C : Linear Approximation
Bi = Ai − i と定義すれば、問題は、自由に整数 b を選び、abs(Bi − b) の総和を最小化する問 題です。ここで、b を Bi の中央値にするのが最適であることがわかります。中央値でない場合は、 中央値に近づけることで損をしないことからこれはわかります。よって、Bi をソートして中央値 を求め、実際に答えを計算すればよいです。ソートがボトルネックとなり、この問題は O(NlogN) で解けます。

解説後

Biを求めるまではあっていた。
中央値を取るといい ?

コメント

は????
難しい。
中央値という発想はなかった。
中央値から削ったらなぜいい感じに最小になるのか未だ理解できず。