Количество перестановок массива с максимальной суммой MEX массивов префиксов

Учитывая массив arr размера N , задача состоит в том, чтобы найти количество его перестановок, чтобы сумма MEX его массивов префиксов была максимальной.

Примечание. MEX набора целых чисел определяется как наименьшее неотрицательное целое число, не принадлежащее этому набору.

Пример:

Input: arr[] = {1, 0, 1}
Output: 2
Explanation: 
All permutations and their MEXs are as follows:
[0, 1, 2]  => array : {1, 0, 1}, MEX({1}) + MEX({1, 0}) + MEX({1, 0, 1}) = 0 + 2 + 2 = 4
[0, 2, 1]  => array : {1, 1, 0}, MEX({1}) + MEX({1, 1}) + MEX({1, 1, 0}) = 0 + 0 + 2 = 2
[1, 0, 2]  => array : {0, 1, 1}, MEX({0}) + MEX({0, 1}) + MEX({0, 1, 1}) = 1 + 2 + 2 = 5
[1, 2, 0]  => array : {0, 1, 1}, MEX({0}) + MEX({0, 1}) + MEX({0, 1, 1}) = 1 + 2 + 2 = 5
[2, 0, 1]  => array : {1, 1, 0}, MEX({1}) + MEX({1, 1}) + MEX({1, 1, 0}) = 0 + 0 + 2 = 2
[2, 1, 0]  => array : {1, 0, 1}, MEX({1}) + MEX({1, 0}) + MEX({1, 0, 1}) = 0 + 2 + 2 = 4
Hence the maximum sum is 5 and the number of permutations with this sum are 2. 

Input: arr[] = {0, 1, 2, 2, 5, 6}
Output: 12

Подход:

Оптимальная идея основана на наблюдении, что сумма MEX массивов префиксов будет максимальной, когда все отдельные элементы расположены в возрастающем порядке, а дубликаты присутствуют в конце массива (например, 0, 1, 2, 3, …). Как только эта непрерывность прерывается, MEX остальных после этого момента остается прежним. Например, в {0, 1, 2, 2, 5, 6} MEX массивов префиксов представляют собой {1, 2, 3, 3, 3, 3}, в которых непрерывность прерывается в индексе 3.

Теперь, чтобы найти количество всех перестановок с максимальной суммой MEX, сохраните частоту элементов на карте. В максимальном массиве префиксов MEX первая позиция всегда заполняется 0, затем вторая 1, третья 2 и так далее. Поэтому попытайтесь заполнить их количеством доступных вариантов, и как только будет достигнута точка, в которой прерывается непрерывность, MEX всех перестановок после этой точки будет одинаковым, и элементы после этого могут быть расположены в любой возможной перестановке. Теперь, чтобы лучше понять это, предположим, что в массиве присутствуют числа от 0 до Y, затем непрерывность прерывается, и после этого присутствует еще K элементов. Тогда количество перестановок с максимальной суммой MEX равно:

ans = frequency[0] * frequency[1] * frequency[2] * … * frequency[Y] * factorial[K]

Теперь, в случае {0, 1, 2, 2, 5, 6}, массив, имеющий максимальную сумму MEX своих массивов префиксов, может:

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

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

1. Объявите карту mp для хранения частоты элементов.
2. Теперь создайте переменную cnt для отслеживания элементов, присутствующих справа от элемента, и инициализируйте ее значением N, т.е. общим количеством присутствующих элементов.
3. Также объявите переменную an для хранения ответа и инициализируйте ее значением 1.
4. Теперь начните итерацию от 0 до размера заданного массива, т.е. от i = 0 до i < n :
   • Если mp[i] != 0, это означает, что до этого момента преобладает непрерывность, и все возможные варианты (т.е. mp[i]) должны быть рассмотрены. Итак, ans станет ans=ans*mp[i] и уменьшит cnt на 1, чтобы получить элементы, находящиеся справа от следующего элемента.
   • Если mp[i] == 0, это означает, что здесь непрерывность прерывается и элементы после этого могут располагаться в любой возможной перестановке. Итак, здесь разрывается цикл и рассматриваются все возможные перестановки элементов, присутствующих справа от этой точки, т.е. факториал cnt.
5. Выведите ответ в соответствии с приведенным выше наблюдением.

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

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