Минимизация затрат на сортировку заданного массива путем сортировки несортированных подмассивов

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

Учитывая массив arr[] размера N , задача состоит в том, чтобы минимизировать стоимость сортировки массива путем сортировки любого несортированного подмассива, где стоимость операции представляет собой разницу между максимальным и минимальным элементом этого подмассива. Эту операцию можно выполнять бесконечное количество раз, включая 0.

Примеры:

Input: arr[] = {1, 7, 5, 2, 1, 8}
Output: 6
Explanation: The subarray from index [1,4] can be chosen and can be sorted with cost = 7 – 1 = 6

Input: arr[] = { 1, 4, 3, 5, 6 ,13, 10}
Output: 4
Explanation: The subarray from index index [1,2] and [5,6] can be sorted with cost of  4 – 3 and 13 – 10 = 1 + 3 = 4

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

Выполните следующие действия, чтобы решить вышеуказанную проблему:

  • Инициализируйте вектор v , скопируйте в него arr и присвойте размер вектора переменной n.
  • Теперь отсортируйте вектор v .
  • Инициализируйте 2 мультимножества m1 и m2 для хранения несортированного и отсортированного подмассива соответственно, а стоимость = 0 для сохранения результата.
  • Теперь перебираем диапазон [0,N) и проверяем
  • Если v[i] не равно arr[i]
  • Вставьте arr[i] в m1 и v[i] в m2
  • Когда оба набора одинаковы, добавьте к стоимости разницу между последним и первым элементом набора.
  • Очистите оба мультимножества, чтобы они использовались следующим несортированным подмассивом.
  • Распечатайте стоимость .

Ниже приведена реализация описанного выше подхода.


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

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