Увеличьте количество карточных колод, которые могут быть сформированы из карт данного типа и джокера.

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

Даны целое число N , обозначающее количество карт в определенной колоде, и массив arr[] размера N , где i -й элемент обозначает частоту i -го типа карт. Также даны K Jokers. Задача состоит в том, чтобы найти максимально возможные действительные колоды с заданными данными.

Действительная колода должна соответствовать одному из двух упомянутых условий:
1. Колода, содержащая ровно по одной карте каждого типа и без джокеров.
2. Колода, содержащая ровно по одной карте каждого типа, кроме одной, и ровно один джокер.

Примеры :

Input: N = 2, arr[] = {10, 15}, K = 3
Output: 13
Explanation: Below are the ways in which 13 decks are made: 
10 decks of type {1, 2}
3 decks of type {J, 2} 
Therefore maximum possible number of decks are 10 + 3 = 13 decks.

Input: N = 3, arr[] = {1, 2, 3}, K = 4
Output: 3
Explanation: Below are the ways in which 13 decks are made:
1 deck of type {1, 2, 3}
1 deck of type {J, 2, 3}
1 deck of type {J, 2, 3}
Therefore maximum possible number of decks are 1+1+1 = 3 decks.

Подход : Данная проблема может быть решена с помощью алгоритма жадного подхода и бинарного поиска. Выполните следующие шаги, чтобы решить данную проблему.

  • Отсортируйте заданный массив arr[] в порядке неубывания.
  • бинарный поиск может быть применен к ответу, чтобы получить максимальное значение.
  • Инициализируйте две переменные, скажем, L = 0 и R = max_element (arr) + K + 1 , которые будут определять начальный диапазон ответа, который нужно найти.
  • Итерировать, пока L +1 < R
    • Инициализируйте переменную, скажем, mid = (L + R)/2 , чтобы отслеживать средний элемент в диапазоне на каждой итерации.
    • Использовать переменная, скажем, need = 0 для подсчета дополнительных карт, необходимых для текущей середины элемент.
    • перебрать весь массив arr[] с переменной i :
      • if arr[i] < mid set need = need + arr[i] – mid.
      • если need <= mid и need <= k , установите L = mid .
      • в противном случае установите R = mid .
  • Наконец, окончательный ответ будет сохранен в L , поэтому верните L в качестве ответа.

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

Временная сложность : O(N(log(N) + log(M + K)), где M — максимальный элемент массива.
Вспомогательное пространство: O(1)

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