Максимальная стоимость значения в диапазоне [1, N], при котором значения лежат не более чем в K заданных диапазонах.
Для заданного положительного целого числа N и массива arr[] размера M типа {L, R, C} , где C — стоимость выбора элемента в диапазоне [L, R] и положительного целого числа K , задача состоит в том, чтобы найти максимальную стоимость значения в диапазоне [1, N] так, чтобы значения находились не более чем в K заданном диапазоне arr[] .
Примеры:
Input: arr[] = {{2, 8, 800}, {6, 9, 1500}, {4, 7, 200}, {3, 5, 400}}, K = 2
Output: 2300
Explanation:
The item chosen is 6 and the costs chosen are 0th and 1st indices such that the 6 belongs into the range of 2 to 8 and 6 to 9. Therefore the total sum of the costs 800 + 1500 is 2300, which is maximum.Input: arr[] = {{1, 3, 400}, {5, 5, 500}, {2, 3, 300}}, K = 3
Output: 700
Подход: данная проблема может быть решена путем сохранения всех затрат для каждого элемента i , лежащего в диапазоне интервалов от L до R, и сортировки выбранных затрат в порядке невозрастания. Затем сравниваем сумму первых K стоимостей всех предметов. Можно выполнить следующие шаги:
- Инициализируйте переменную, скажем, totMaxSum = 0 , чтобы сохранить максимальную сумму стоимости.
- Инициализируйте переменную, скажем, sum = 0 , чтобы сохранить сумму стоимости i -го предмета.
- Инициализируйте вектор, скажем, currCost , чтобы сохранить стоимость i -го элемента.
- Выполните итерацию в диапазоне [1, N], используя переменную i , и вложенную итерацию в диапазоне [0, M – 1], используя переменную j , и выполните следующие шаги:
- Если значение i находится в диапазоне [arr[i][0], arr[i][1]] , затем добавьте значение arr[i][2] к вектору currCost .
- Отсортируйте вектор currCost в порядке невозрастания.
- Переберите вектор currCost и добавьте значения первых K элементов к sum .
- Обновите значение totMaxSum на max(totMaxSum, sum) .
- После выполнения вышеуказанных шагов выведите значение totMaxSum как максимальную сумму.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M*log M)
Вспомогательное пространство: O(N*M)