Оставить в массиве k различных чисел

Рейтинг: -1Ответов: 1Опубликовано: 07.05.2023

В университете дали задание, не могу придумать как решить: Дан массив длины n, нам при помощи двух действий (прибавление к наименьшему элементу массива единицы или вычитание из наибольшего элемента 1) надо сделать так, чтобы в массиве после всех действий осталось k различных чисел. То есть, из массива -1; -5; 7; 8; 2; 1; 10, надо получить -1; -1; 7; 7; 7; 2; 1. Может кто встречался с подобным, а то из идей была только сортировка, но я не понимаю, что делать с этим дальше...

алгоритм олимпиада сортировка динамическое-программирование
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Хорошо, отсортировали по возрастанию.

Теперь используем метод двух указателей.

Левый индекс поставим на 0, правый тоже, и начнём двигать правый, пока в окне между двух указателей от L до R-1 не будет ровно k различных элементов.

Теперь посчитаем сумму значений справа RSum, и сколько нужно от значений справа отнять единиц, чтобы все правые элементы стали как R-1-ый, это начальное значение для

MinOnes = RSum - A[R-1]*(n-R)

Начинаем двигать левый указатель, пока количество различных элементов в окне не станет меньше k, при этом считая сумму, оставшуюся слева LSum.

Продолжим двигать правый, как и раньшe, уменьшая RSum. При остановке правого посчитаем необходимое количество единиц и сравним с MinOnes

Ones = (RSum - A[R-1]*(n-R)) + ((A[L]*(L-1) - LSum))

Повторяем продвижение окна, содержащего ровно k различных элементов, до конца.