Максимально увеличьте количество ящиков, необходимых для хранения хотя бы одной черной и одной белой рубашки.

Даны три числа W , B и O , представляющие количество рубашек белого, черного и других цветов соответственно, задача состоит в том, чтобы найти максимальное количество требуемых коробок, чтобы каждая коробка содержала три рубашки, состоящие как минимум из одной белой и одной черной рубашки, используя заданное количество рубашек.

Примеры:

Input: W = 3, B = 3, O = 1
Output: 2
Explanation:
Below are the distribution of shirts in the boxes:
Box 1: 1 white shirt, 1 black shirt and 1 shirt of other color.
Box 2: 2 white shirts and 1 black shirt.
Box 3: 1 black shirt
Since, only 2 boxes satisfy the given condition which is the maximum possible number of boxes with the given quantity of shirts. Therefore, print 2.

Input: W = 4, B = 6, O = 0
Output: 3

Подход: Данную проблему можно решить с помощью бинарного поиска. Идея состоит в том, чтобы найти максимальное количество ящиков в пространстве поиска, образованном нижней и верхней границей. Можно заметить, что нижняя граница и верхняя граница количества ящиков равны 0 и минимуму W и B соответственно. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как 0 , чтобы сохранить требуемый результат.
• Инициализируйте две переменные, скажем, low как 0 и high как минимум (W, B).
• Цикл, пока значение low не станет меньше high , и выполните следующие шаги:
  • Найдите среднее значение low и high в переменной, скажем, mid .
  • Проверьте, может ли максимальное количество полей равняться mid , затем обновите значение ans до mid и обновите пространство поиска в правой половине, обновив значение low .
  • В противном случае обновите пространство поиска до левой половины, обновив значение high .
• Выведите значение ans в качестве результата.

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

Временная сложность: O (log (мин (W, B)))
Вспомогательное пространство: O(1)