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

Пусть x текущий элемент, а y, предыдущее значение, тогда возможны три случая:

• x - r > y, тогда предположим, что элемент x был равен x - r в первоначальном массиве.
• x + r < y, тогда все числа из диапазона [x - r;x + r], уже были получены на предыдущих элементах, а значит, элемент x никак не привести к уникальному.
• иначе можем предположить, что вместо x раньше было значение y + 1, поставим его в ответ.

Соответственно, ответ — это сумма первых и третьих случаев, однако можно было сначала поставить числа таким способом, а потом уже посчитать ответ.

Для доказательства оптимальности данного подхода рассмотрим два числа x₀ и x₁, такие что x₀ < x₁. Очевидно, что пересечение диапазонов [x₀ - r;x₀ + r] и [x₁ - r;x₁ + r] не выгодно занимать при рассмотрении x₀, так как мы уменьшим количество возможных вариантов для x₁. В случае же, если мы возьмем минимальное число из [x₀ - r;x₀ + r], которое до этого не брали, мы оставим наибольшее возможное количество вариантов для x₁.

Сложность решения .