Калькулятор максимальных чаевых | Набор 2

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

Рахул и Анкит — единственные два официанта в Королевском ресторане. Сегодня в ресторан поступило N заказов. Количество чаевых может различаться, если его обрабатывают разные официанты и задают в виде массивов A[] и B[] , так что, если Рахул возьмет i -й заказ, он получит чаевые на A[i] рупий, а если Анкит примет этот заказ, чаевые будут B[i] рупий. Чтобы максимизировать общую сумму чаевых, они решили распределить заказ между собой. Один заказ будет обрабатываться только одним человеком . Кроме того, из-за нехватки времени Рахул не может выполнять более X заказов, а Анкит не может выполнять более Y заказов. Гарантируется, что X + Y больше или равно N , что означает, что все заказы могут быть обработаны либо Рахулом, либо Анкитом. Задача состоит в том, чтобы узнать максимально возможную сумму общих денег чаевых после обработки всех заказов.

Примеры:

Input: N = 5, X = 3, Y = 3, A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}
Output: 21
Explanation:
Step 1: 5 is included from Ankit’s array 
Step 2: 4 is included from Ankit’s array 
Step 3: As both of them has same value 3 then choose any one of them 
Step 4: 4 is included from Rahul’s array 
Step 5: 5 is included from Rahul’s array 
Therefore, the maximum possible amount of total tip money sums up to 21.

Input: N = 7, X = 3, Y = 4, A[] = {8, 7, 15, 19, 16, 16, 18}, B[] = {1, 7, 15, 11, 12, 31, 9} 
Output: 110

Наивный подход: наивный подход к решению этой статьи обсуждался в предыдущей статье.

Эффективный подход: Идея состоит в том, чтобы использовать жадный метод для решения проблемы. Отсортируйте N заказов в порядке убывания на основе разницы между советом Рахула и советом Анкита. Затем пройтись по всем ордерам и взять максимальную чаевую i -го ордера, если это возможно. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте ans как 0, чтобы сохранить максимально возможный наконечник.
  • Создайте вектор из пары целых чисел V размера N , так что первый и второй элементы V[i] хранят вершину i -го порядка Рахула и Анкита соответственно.
  • Отсортируйте вектор V в порядке убывания на основе разницы между кончиками.
  • Пройдите вектор V , используя переменную i
    • Если значение Y равно 0 ИЛИ выполняется условие V[i].first ≥ V[i].second , то добавьте значение V[i].first к ans и уменьшите X на 1 .
    • В противном случае добавьте значение V[i].second к ans и уменьшите Y на 1 .
  • После выполнения вышеуказанных действий распечатайте значение ответа в качестве результата.

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


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

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