Переупорядочить массив, чтобы максимизировать сумму MEX всех подмассивов, начиная с первого индекса
Учитывая массив arr[] из N элементов в диапазоне от 0 до N-1 (оба включены), задача состоит в том, чтобы переупорядочить массив таким образом, чтобы сумма всех MEX из каждого подмассива, начиная с индекса 0, была максимальной. В массиве могут быть дубликаты.
MEX of an array is the first non-negative element that is missing from the array.
Примеры:
Input: N = 3, arr[] = {2, 1, 0}
Output: 6
Explanation: Initially for subarray {2} the missing element is 0.
For {2, 1} the missing element is 0, and for {2, 1, 0} the missing element is 3.
In this way the answer is 0 + 0 + 3 = 3.
But if the array is rearranged like {0, 1, 2}, the answer will be 1 + 2 + 3 = 6.Input: N = 5, arr[] = {0, 0, 0, 0, 0}
Output: 5
Подход:
The idea is to put the smaller elements in the beginning of new array to get highest possible missing whole numbers for each subarray, but if we have duplicates then the duplicates would be inserted in the end of the new array.
Следуйте инструкциям, чтобы решить проблемы:
- Отсортируйте массив.
- Инициализируйте 2 переменные cur для хранения текущего наименьшего пропущенного целого числа и count для хранения количества раз, когда наименьшее целое число будет наименьшим для следующих подмассивов.
- Если текущий элемент больше, чем cur , то для всех следующих подмассивов наименьшее целое число будет cur , так как массив отсортирован. Поэтому добавьте количество оставшихся подмассивов, чтобы подсчитать и разорвать цикл.
- В противном случае, если мы найдем дубликаты, увеличим переменную count, чтобы добавить значение в конце.
- В противном случае для каждого индекса обновите cur и добавьте значения в переменную ans , которая будет содержать окончательный ответ.
- В конце концов, если cur не равно 0, это означает, что существуют подмассивы, в которых cur является наименьшим целым числом и которые не добавляются к ответу, поэтому добавьте cur * count к ответу и верните его.
Иллюстрация:
Consider N = 6, arr[] = {4, 2, 0, 4, 1, 0}
Initialize, ans = 0, cur = 0, count = 0
Sort the array, so arr[] = {0, 0, 1, 2, 4, 4}
For index 0:
=> arr[i] = cur,
=> thus cur would be cur + 1 = 1
=> ans would be ans + cur = 0 + 1 = 1For index 1:
=> arr[i] = cur – 1
=> Means it is a duplicate
=> Increase the count variable, count = 0 + 1 = 1For index 2:
=> arr[i] = cur
=> cur would be cur + 1 = 2
=> ans would be ans + cur = 1 + 2 = 3For index 3:
=> arr[i] = cur,
=> Thus cur would be cur + 1 = 3
=> ans would be ans + cur = 3 + 3 = 6For index 4:
=> arr[i] > cur
=> cur would be the same for all the remaining subarrays.
=> Thus, count = count + 6 – 4 = 1 + 2(remaining subarrays) = 3 and break the loop.In the end add cur * count to ans, thus ans = 6 + 3 * 3 = 15
Ниже приведена реализация этого подхода:
Временная сложность: O(N * log N)
Вспомогательное пространство: O(1)