Максимизируйте сумму массива, заменив не более L элементов на R для Q запросов

Опубликовано: 21 Сентября, 2022

Дан массив arr[] , состоящий из N целых чисел, и массив Query[][] , состоящий из M пар типа {L, R} , задача состоит в том, чтобы найти максимальную сумму массива, выполнив запросы Query[][ ] таким образом, что для каждого запроса {L, R} заменяется не более L элементов массива на значение R .

Примеры:

Input: arr[]= {5, 1, 4}, Query[][] = {{2, 3}, {1, 5}}
Output: 14
Explanation:
Following are the operations performed:
Query 1: For the Query {2, 3}, do nothing.
Query 2: For the Query {1, 5}, replace at most L(= 1) array element with value R(= 5), replace arr[1] with value 5.
After the above steps, array modifies to {5, 5, 4}. The sum of array element is 14, which is maximum.

Input: arr[] = {1, 2, 3, 4}, Query[][] = {{3, 1}, {2, 5}}
Output: 17

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

  • Поддерживайте приоритетную очередь с минимальной кучей и храните все элементы массива.
  • Проходим по заданному массиву запросов Q[][] и для каждого запроса {L, R} выполняем следующие шаги:
    • Измените значение не более чем L элементов меньше, чем R до значения R , начиная с наименьшего.
    • Выполните описанную выше операцию, извлеките элементы меньше R и поместите R на их места в очереди приоритетов.
  • После выполнения вышеуказанных шагов выведите сумму значений, хранящихся в очереди приоритетов, как максимальную сумму.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M*N*log N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ