Разобьем максимальный элемент на N групп так, чтобы разница между полученным и требуемым не превышала K

Опубликовано: 25 Февраля, 2023

Даны два массива A[] и B[] размера N и M соответственно, обозначающие требуемые элементы каждой группы и количество элементов в упаковке соответственно. Задача состоит в том, чтобы распределить максимальное количество пачек так, чтобы разница между количеством элементов, полученных группой, и их потребностью не превышала K .

Примеры:

Input: N = 4, M = 3, K = 5, A[] = [60, 45, 80, 60], B[] = [30, 60, 75]
Output: 2
Explanation: The 2 packs that will be distributed are as follows.
The pack whose size is 60 is distributed among the group with
requirement 60 as 60 – 5 < 60 and 60 + 5 > 60 .
The pack whose size is 75 is distributed among the group with
requirement 80 as 80 – 5 = 75 and 80 + 5 > 75.

Input: N = 4, M = 3, K = 10, A[] = [60, 40, 80, 60], B[] = [30, 60, 75]
Output: 3
Explanation: All the packs will be distributed in this situation .
The pack whose size is 30 is distributed among the group with
requirement 40 as 40 – 10 = 30 and 40 + 10 > 30.
The pack whose size is 60 is distributed among the group with 
requirement 60 as 60 – 10 < 60 and 60 + 10 > 60.
The pack whose size is 75 is distributed among the group with 
requirement 80 as 80 – 10 < 75 and 80 + 10 > 75.

Подход: Задачу можно решить с помощью сортировки, основанной на следующей идее:

Sort both arrays. Now greedily find out the first group with a requirement that is fulfilled and among all the possible packs, allot the pack with minimum number of elements so that options are available for groups with higher requirements.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Сортировка массива A[] и B[].
  • После сортировки обоих массивов используйте два указателя i и j для итерации A и B соответственно.
  • Инициализируйте переменную (скажем, cnt = 0), чтобы сохранить ответ.
  • Теперь начните перебирать массивы:
    • Если для группы требуется размер пакета, увеличьте cnt, i и j .
    • Если потребность группы после вычитания максимальной разницы K больше размера пакета, то этот пакет бесполезен ни для одной группы. Следовательно, приращение j .
    • Если размер пакета больше, чем требуется группе после добавления K , то для этой группы нет пакета. Следовательно, приращение i .
  • Верните переменную cnt в качестве требуемого ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(D * logD), где D — максимум между N и M.
Вспомогательное пространство: O(1)

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