C: Linear Approximation - AtCoder Regular Contest 100
B[i] = A[i] - iとおく。 入力例2ではB[i]は以下のような値をとっている。なお図ではb=2と仮置きしている。 であるから、 これは上図では点と直線y=bの距離の和を求めればいいことがわかる。 直線bを上下に動かしてみると以下の事がわかる。
- 一番上の点よりも上に直線を持っていっても意味がない。
- 一番下の点よりも下に直線を持っていっても意味がない。
- 上の点が下の点よりも数が多い時、直線を上に持っていったほうがいい。
- 下の点が上の点よりも数が多い時、直線を下に持っていったほうがいい。
- 上の点と下の点の数が等しい時、直線を上下しても結果は変わらない。
よって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;