9023. Минимум увеличений

Задан массив из n натуральных чисел. Найдите наименьшее количество операций, при помощи которых его можно преобразовать в арифметическую прогрессию с разностью 1. Одна операция состоит в увеличении любого элемента на 1.

Вход. Первая строка содержит число n (n ≤ 10⁶). Вторая строка содержит n натуральных чисел, каждое из которых не больше 10⁶.

Выход. Выведите наименьшее количество операций, при помощи которых массив можно преобразовать в арифметическую прогрессию с разностью 1.

Пояснение. В первом тесте массив следует преобразовать в 8 9 10 11 12, выполнив (8 – 3) + (9 – 6) + (10 – 4) + (11 – 11) + (12 – 5) = 5 + 3 + 6 + 0 + 7 = 21 операцию.

Пример входа 1	Пример выхода 1
5 3 6 4 11 5	21
Пример входа 2	Пример выхода 2
5 4 4 5 5 7	5

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Пусть искомое наименьшее количество операций преобразовывает исходный массив m[0], m[1], …, m[n – 1] в x, x + 1, x + 2, …, x + n – 1. Очевидно, что m[0] ≤ x ≤ max(m[0], m[1], …, m[n – 1]).

Последовательность d = [x, x + 1, x + 2, …, x + n – 1] назовем подходящей, если m можно преобразовать в d (для этого должно выполняться m[i] ≤ 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 ≤ x ≤ 7. Например, при x = 4 последовательность d уже является подходящей.

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

Входную последовательность храним в массиве m. Последовательность x, x + 1, x + 2, …, x + n – 1 храним в массиве d.

#define MAX 1000000

int m[MAX], d[MAX];

Функция check в массиве d генерирует последовательность first, first + 1, first + 2, …, first + n – 1. Если для каждого i (0 ≤ i ≤ n – 1) выполняется неравенство m[i] ≤ 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);