Мінімальна вартість відрізка#13042
Увійти

Мінімальна вартість відрізка (Розбір)

Розв'язання

Нехай

b_i = a_i - c_i.

Припустимо, що ми вибрали відрізок [l,r] довжини . Тоді

r = l + k - 1.

Вартість цього відрізка дорівнює

\sum_{i=1}^{n} |b_i - b_l + d_i|.

Розглянемо всі позиції у трьох випадках.

Якщо i < l, то d_i = l-i, тому

b_i-b_l+d_i = b_i-b_l+l-i = (b_i-i)-(b_l-l).

Отже, внесок усіх таких позицій дорівнює

\sum_{i<l}|(b_i-i)-(b_l-l)|.

Якщо l \le i \le r, то d_i=0, тому внесок дорівнює

\sum_{l\le i\le r}|b_i-b_l|.

Якщо i>r, то d_i=i-r, тому

b_i-b_l+d_i = b_i-b_l+i-r = (b_i+i)-(b_l+r).

Отже, внесок цих позицій дорівнює

\sum_{i>r}|(b_i+i)-(b_l+r)|.

Таким чином, повна вартість відрізка [l,r] дорівнює

\sum_{i<l}|(b_i-i)-(b_l-l)| + \sum_{l\le i\le r}|b_i-b_l| + \sum_{i>r}|(b_i+i)-(b_l+r)|.

Відрізок повинен задовольняти умову

2 \le l \le r \le n-1.

Оскільки r=l+k-1, достатньо перебрати

2 \le l \le n-k.

Маємо лише можливих відрізків.

Для кожного з них можемо пройтися по всіх позиціях і безпосередньо порахувати його вартість за .

Отже, розв'язання за O(n^2) достатньо для n \le 3000.

Оскільки відповідь може бути значно більшою за 2^{31}, потрібно використовувати long long.

Доведення коректності

Для кожного допустимого відрізка [l,r] ми точно обчислюємо значення

\sum_{i=1}^{n}|b_i-b_l+d_i|

окремо розглядаючи випадки i<l, l\le i\le r та i>r.

Ці три випадки покривають усі позиції рівно по одному разу.

Ми перебираємо кожен допустимий відрізок довжини , тому мінімальне знайдене значення є шуканою відповіддю.

Складність

Існує допустимих відрізків, і кожен з них обробляється за .

Отже, загальна складність становить

O(n^2)

за часом та

за пам'яттю.