Мінімум збільшень (Розбір)

Нехай мінімальна кількість операцій перетворює початковий масив

в арифметичну прогресію виду

Очевидно, що m[0] \le x \le max(m[0], m[1], ..., m[n - 1]).

Назвемо послідовність

підходящою, якщо масив $m$ можна перетворити у $d$, тобто якщо виконується умова m[i] \le d[i] для всіх $i$ від $0$ до n - 1.

Залишається знайти найменше значення $x$, при якому послідовність $d$ буде підходящою. Це можна зробити за допомогою бінарного пошуку.

Приклад

Розглянемо перший тест. Нехай d = [x, x + 1, x + 2, ..., x + n - 1] — підходяща послідовність з мінімальною сумою елементів.

Очевидно, що m[0] = 3 ≤ x ≤ 11 = max(m[i]).

Бінарним пошуком знаходимо найменше значення $x$, при якому послідовність $d$ є підходящою.

Наприклад, при x = 6 послідовність $d$ не буде підходящою, а при x = 8 буде.

Розглянемо другий тест. Бінарний пошук запускаємо на проміжку 4 \le x \le 7. Наприклад, вже при x = 4 послідовність $d$ є підходящою.

Реалізація алгоритму

Вхідну послідовність зберігаємо в масиві $m$. Послідовність x, x + 1, x + 2, ..., x + n - 1 зберігаємо в масиві $d$.

#define MAX 1000000
int m[MAX], d[MAX];

Функція check генерує в масиві $d$ послідовність виду

Якщо для кожного i~(0 \le i \le n - 1) виконується нерівність m[i] \le d[i], то масив $d$ можна отримати з масиву $m$, збільшуючи окремі елементи на $1$. У цьому випадку масив $d$ називається підходящим.

Якщо масив $d$ є підходящим, то функція check повертає $1$, в іншому випадку — $0$.

int check(int first)
{
  for (int i = 0; i < n; i++)
    d[i] = first++;
  for (int i = 0; i < n; i++)
    if (m[i] > d[i]) return 0;
  return 1;
}

Основна частина програми. Читаємо вхідне значення $n$. Обчислюємо максимальне значення $mx$ в масиві $m$.

scanf("%d", &n);
mx = 0;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  if (m[i] > mx) mx = m[i];
}

start = m[0];
end = mx;

Запускаємо бінарний пошук значення $x$ в інтервалі [start; end] = [m[0]; mx].

Шукаємо мінімальне значення $x$, при якому послідовність x, x + 1, x + 2, ..., x + n - 1 може бути отримана з масиву m[0], m[1], ..., m[n - 1].

while (start < end)
{
  mid = (start + end) / 2;
  if (check(mid))
    end = mid;
  else
    start = mid + 1;
}

Генеруємо шукану арифметичну прогресію.

for (i = 0; i < n; i++)
  d[i] = start++;

Обчислюємо мінімальну кількість операцій, необхідних для отримання прогресії.

op = 0;
for (int i = 0; i < n; i++)
  op += (d[i] - m[i]);

Виводимо відповідь.

printf("%lld\n", op);