Максимальное количество манго, которое можно купить

Имея два целых числа W и C , представляющих количество арбузов и монет, задача состоит в том, чтобы найти максимальное количество манго, которое можно купить, учитывая, что каждое манго стоит 1 арбуз, а X монет и y монет можно заработать, продав арбуз.

Примеры:

Input: W = 10, C = 10, X = 1, Y = 1
Output: 10
Explanation: The most optimal way is to use 10 watermelons and 10 coins to buy 10 mangoes. Hence, the maximum number of mangoes that can be bought is 10.

Input: W = 4, C = 8, X = 4, Y = 4
Output: 3
Explanation: The most optimal way is to sell one watermelon. Then, the number of coins increases by 4. Therefore, the total number of coins becomes 12. Therefore, 3 watermelons and 12 coins can be used to buy 3 mangoes. Hence, the maximum number of mangoes that can be bought is 3.

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

• Инициализируйте переменную как 0 , чтобы сохранить требуемый результат.
• Инициализируйте две переменные l как 0 , r как W для хранения граничных областей пространства поиска для бинарного поиска.
• Зациклить, пока l≤r , и выполнить следующие шаги:
  • Сохраните среднее значение в переменной mid как (l+r)/2 .
  • Проверьте, можно ли купить среднее количество манго, используя заданные значения W , C , x и y .
  • Если это правда, то обновите an до mid и выполните поиск в правой части mid , обновив l до mid+1 . В противном случае обновите значение r до mid-1 .
• Выведите значение ans в качестве результата.

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

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