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

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

Дан массив arr длины N со значениями 1 и 2, указывающими элементы типа 1 и типа 2, и два игрока, player1 и player2. Задача состоит в том, чтобы найти минимальное количество монет, необходимое для удаления всех элементов в порядке, указанном в массиве. Необходимо соблюдать следующие правила:

  • Игрок1 и Игрок2 по очереди удаляют элементы, причем Игрок1 начинает первым.
  • Оба могут удалить не более 2 соседних элементов и должны удалить хотя бы один элемент в свой ход.
  • Элемент типа 2 может быть удален обоими без монеты
  • Элемент типа 1 может быть удален Игроком 2 без монеты, но Игроку 1 потребуется монета для удаления элемента.

Пример:

Input: N = 8 arr = [1, 2, 1, 1, 2, 1, 1, 1]
Output: 2
Explanation: Total coins needed by Player1 is 2. Below are the elements removed at each player’s turn:

  • Player1 will remove the first element of type 1 using one coin and second element of type 2 without a coin
  • Player2 will remove the next two elements
  • Player1 will start its operation and remove only the next element of type 2 without a coin
  • Player2 will start its operation and remove next two elements at index 5 and 6 in the array
  • Player1 will remove the last element of type 1 using one coin

Input: N = 4 arr = [1, 1, 2, 2]
Output: 2
Explanation: Total coins needed by Player1 is 1.  Below are the elements removed at each player’s turn

  • Player1 will remove the first element of type 1 using one coin
  • Player2 will remove the 2nd and the 3rd element
  • Player1 will remove the 4th element of type 2 without a coin

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

  • Первый элемент рассматривается отдельно. Если это тип 1, то 1 будет добавлено к общему количеству монет, необходимых для удаления элементов.
  • Перебрать массив со 2-го индекса, учитывая ход Player1.
  • Если на ходу Player1 первый элемент имеет тип 2, а следующий элемент типа 1, то Player1 удалит только элемент типа 2, а затем Player2 может начать операцию.
  • Если на ходу Player1 и два последовательных элемента типа 2, то в этой операции Player1 удалит оба элемента
  • Если на ходу Игрока 1 есть 3 последовательных элемента типа 1, то Игрок 1 удалит только первый элемент, используя одну монету, а следующие два элемента могут быть удалены Игроком 2.
  • Учитывая три приведенных выше случая, можно сделать наблюдение, что каждый блок элементов типа 1 начинается с операции Player2.
  • Таким образом, для каждых трех последовательных элементов типа 1 видно, что игроку 1 требуется одна монета для удаления элемента, а два элемента будут удалены игроком 2.

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

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