AtCoder Regular Contest 100: C - Linear Approximation

solution

$a_i \gets a_i - i$と取り直し(典型 1)てその中央値(典型 2)が$b$。 中央値でいいことの証明は$\pm 1$してみたときの差を考えればすぐで、ここから$N$が偶数のときに雑にやってよいことも言える。 $O(N \log N)$。

implementation

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i
a.sort()
b = a[n // 2]
answer = 0
for a_i in a:
    answer += abs(a_i - b)
print(answer)