はまやんはまやんはまやん

hamayanhamayan's blog

Linear Approximation [AtCoder Regular Contest 100 C]

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

解法

https://beta.atcoder.jp/contests/arc100/submissions/2793786

abs(A[1]-(b+1)) + abs(A[2]-(b+2)) + ... + abs(A[N] - (b + N))を変形しよう。
すると、abs( (A[1]-1)-b) + abs( (A[2] - 2) - b) + ... + abs( (A[N]-N) - b)となる。
B[i] = A[i] - iとするとabs(B[1] - b) + abs(B[2] - b) + ... + abs(B[N] - b)を最小化する問題となる。
これには「マンハッタン距離の差の総和を最小化するときは中央値を使う」という典型がある。
中央値を使って最小値を求めよう。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        cin >> A[i];
        A[i] -= (i + 1);
    }
    sort(A, A + N);
 
    int b;
    if (N % 2 == 1) b = A[N / 2];
    else b = (A[N / 2 - 1] + A[N / 2]) / 2;
 
    ll ans = 0;
    rep(i, 0, N) ans += abs(A[i] - b);
    cout << ans << endl;
}