問題概要

長さ $N$ の整数列 $A_{1}, \dots, A_{N}$ が与えられます。整数 $b$ をいろいろ変えたときの

$| A_{1} - (b + 1) | + | A_{2} - (b + 1) | + \dots + | A_{N} - (b + N) |$

の最小値を求めてください。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

非本質だけど、 $b$ って普通「変数」じゃなくて「定数」に使う記号じゃん。なので、紛らわしいので $b$ じゃなくて $x$ にしてみよう。(非本質なんだけど、こういうの意外と大事だと思う)。

$| A_{1} - (x + 1) | + | A_{2} - (x + 1) | + \dots + | A_{N} - (x + N) |$

そして、この式だと、数列 $A_{1}, \dots, A_{N}$ が主役っぽくなっているので、 $x$ を主役に書き換えてみます。 $| A_{i} - (x + i) | = | -x + (A_{i} - i) | = | x - (A_{i} - i) |$ であることから、こんな風に書き換わります

$| x - (A_{1} - 1) | + | x - (A_{2} - 2) | + \dots + | x - (A_{N} - N) |$

だいぶ見やすくなった。さらに、 $B_{i} = A_{i} - i$ とすると

$| x - B_{1} | + | x - B_{2} | + \dots + | x - B_{N} |$

となります。かなり見やすくなった。ここまできたら、もう知っている人は知っていると思う！！！

絶対値の和の最小化

結論からいうと、

$| x - B_{1} | + | x - B_{2} | + \dots + | x - B_{N} |$ を最小にする $x$ は、 $B_{1}, B_{2}, \dots, B_{N}$ のメディアンになります！！！

その証明は、ここにも書きました。

drken1215.hatenablog.com

結論

答えは、

$B_{i} = A_{i} - i$ とおいて
$x$ を $B_{1}, B_{2}, \dots, B_{N}$ のメディアンとして、
$| x - B_{1} | + | x - B_{2} | + \dots + | x - B_{N} |$ の値を求める

とすればよい。計算量は、メディアンを求めるのにソートすることから、 $O(N\log{N})$ となる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i], B[i] = A[i] - i;

    // メディアンを
    sort(B.begin(), B.end());
    long long x = B[N/2];

    // 答えを求める
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        res += max(x - B[i], -x + B[i]); // |A| = max(A, -A)
    }
    cout << res << endl;
}