Максимальное удаление мячей как минимум двух разных типов

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

Дан массив arr[] размера 3 , обозначающий количество шаров типа 1, 2 и 3 соответственно, задача состоит в том, чтобы найти максимальное количество ходов, которое можно сделать, если за один ход три шара, из которых на не менее 2 шаров разных типов удаляются.

Примеры:

Input: arr[] = {2, 3, 3}
Output: 2
Explanation:
Move 1: Remove 1 ball of each type. Therefore, arr[] becomes {1, 2, 2}.
Move 2: Remove 1 ball of each type. Therefore, arr[] becomes {0, 1, 1}.
No further moves can be performed.

Input: arr[] = {100, 1, 2}
Output: 3
Explanation:
Move 1: Remove 1 ball of type 2 and 2 balls of type 1. Therefore, arr[] becomes {98, 0, 2}.
Move 2: Remove 1 ball of type 3 and 2 balls of type 1. Therefore, arr[] becomes {96, 0, 1}.
Move 3: Remove 1 ball of type 3 and 2 balls of type 1. Therefore, arr[] becomes {94, 0, 0}.
No further moves can be performed.

Подход: Идея отсортировать массив по возрастанию, а затем возникает два случая:

  • Если arr[2] меньше 2 * (arr[0] + arr[1]) , ответ будет (arr[0] + arr[1] + arr[2]) / 3 .
  • Если arr[2] больше 2 * (arr[0] + arr[1]) , ответ будет arr[0] + arr[1] .

Выполните следующие шаги, чтобы решить проблему:

  • Отсортируйте массив в порядке возрастания.
  • Выведите минимум (arr[0]+arr[1]+arr[2])/3 и arr[0]+arr[1] .

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

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