C: Linear Approximation - AtCoder Regular Contest 100

B[i] = A[i] - iとおく。 入力例2ではB[i]は以下のような値をとっている。なお図ではb=2と仮置きしている。 であるから、 これは上図では点と直線y=bの距離の和を求めればいいことがわかる。 直線bを上下に動かしてみると以下の事がわかる。

1. 一番上の点よりも上に直線を持っていっても意味がない。
2. 一番下の点よりも下に直線を持っていっても意味がない。
3. 上の点が下の点よりも数が多い時、直線を上に持っていったほうがいい。
4. 下の点が上の点よりも数が多い時、直線を下に持っていったほうがいい。
5. 上の点と下の点の数が等しい時、直線を上下しても結果は変わらない。

よってbの値はBだけ調べればいいことがわかる。

とりあえず、bを一番低い値に設定して解候補を計算してみる。あとは、bを上へずらしていって、差分と上下の点の数を使って、解候補を加減すればいい。

int N;
cin >> N;
vi A(N), B(N), C;
rep(i, N) {
    cin >> A[i];
    B[i] = A[i] - (i + 1);
}
sort(all(B));
C = B;
C.erase(unique(all(C)), C.end());

ll sm = 0;
rep(i, N)sm += B[i] - C[0];
ll re = sm;

ll p = 0;
FOR(i, 1, sz(C)) {
    while (p < N && B[p] < C[i])++p;
    ll q = N - p;
    sm += (p - q) * (C[i] - C[i - 1]);
    smin(re, sm);
}

cout << re << endl;