Шум

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

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

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

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

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