Максимальная стоимость значения в диапазоне [1, N], при котором значения лежат не более чем в K заданных диапазонах.

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

Для заданного положительного целого числа 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)

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