Минимизация затрат на сортировку заданного массива путем сортировки несортированных подмассивов
Учитывая массив 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 = 6Input: 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)