Минимальная стоимость пропуска N человек через заданный туннель

Даны два положительных целых числа X и Y и массив arr[] , состоящий из N положительных целых чисел, такой, что arr[i] представляет рост i ^-го человека и существует туннель высоты H , задача состоит в том, чтобы найти общую минимальную стоимость требуется пройти через заданный туннель все N человек , за один раз могут пройти не более двух человек , сумма высот которых меньше H , по следующим правилам:

• Когда два человека проходят через туннель за раз, то стоимость равна Y .
• Когда один человек проходит через туннель за раз, тогда стоимость равна X .

Примечание. Все элементы массива меньше H .

Примеры:

Input: arr[] = {1, 3, 4, 4, 2}, X = 4, Y = 6, H = 9
Output: 16
Explanation:
Consider the passing of persons according to the below order:

1. Person 1 and Person 4 having heights 1 and 4 respectively has the sum of heights as 1 + 4 = 5 < H(= 9). Therefore, the cost for this operation is Y(= 6).
2. Person 2 and Person 3 having heights 3 and 4 respectively has the sum of heights as 3 + 4 = 7 < H(= 9). Therefore, the cost for this operation is Y(= 6).
3. Person 5 has height 3 which is less than H(= 9). Therefore, the cost for this operation is is X( = 4).

Therefore, the total cost is 6 + 6 + 4 = 16, which is minimum among all possible combinations.

Input: arr[] = {1, 3, 4}, X = 4, Y = 6, H = 9
Output: 10

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

• Отсортируйте заданный массив arr[] по возрастанию.
• Инициализируйте два указателя, скажем, i и j как 0 и (N – 1) соответственно, чтобы они указывали на крайние точки массива.
• Повторяйте до тех пор, пока значение i не станет меньше j, и выполните следующие шаги:
  • Если сумма значений arr[i] и arr[j] меньше, чем H , то увеличивается значение стоимости на Y и увеличивается значение i и уменьшается значение j на 1 .
  • В противном случае уменьшите значение j на 1 и обновите значение стоимости на X .
• Если значения i и j равны, увеличьте значение стоимости на X .
• После выполнения вышеуказанных шагов выведите значение стоимости как результирующую минимальную стоимость.

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

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