Распределите компоненты R,B так, чтобы каждый пакет содержал по крайней мере 1 компонент R и 1 компонент B с абсолютной разницей не более D

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

Даны два положительных целых числа R и B , обозначающие R красных и B синих бобов, и целое число D , задача состоит в том, чтобы проверить, возможно ли распределить бобы по нескольким (возможно, одному) пакетам в соответствии со следующими правилами:

  • В каждом пакете есть как минимум одна красная фасоль.
  • В каждом пакете есть хотя бы одна синяя фасоль.
  • Количество красных и синих бобов в каждом пакете должно отличаться не более чем на D ( или |RB| <= D)

Выведите Да , если это возможно. В противном случае выведите Нет .

Примеры

Input: R = 1, B = 1, D = 0
Output: Yes
Explanation: Form one packet with 1 red and 1 blue bean. The absolute difference |1−1| = 0 ≤ D.

Input: R = 6, B = 1, D = 4
Output: No

Подход: Эту проблему можно легко решить, заметив, что максимум (R и B) равен D + 1 , умноженному на минимум R и B. Следуйте инструкциям ниже, чтобы решить проблему:

  • Найдите максимум R и B. и минимум R и B.
  • Чтобы удовлетворить данным 3 ограничениям, значение max(R, B) должно быть не более чем (D + 1) умножить на min(R, B) , потому что (D + 1) bean-компонентов может храниться в каждом пакете, 1 bean-компонент одного типа и фасоли D другого типа.
  • После выполнения вышеуказанных шагов выведите «Да» , если значение max(R, B) меньше или равно (D + 1)*min(R, B) . В противном случае выведите «Нет» .

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

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

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