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

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

Дан массив arr из N целых чисел и массив ключей, так что ключ для каждого элемента в arr изначально равен его индексу в arr. Учитывая, что можно выполнить определенные ходы, где за один ход выбрать два индекса (i, j) , удалить соответствующие элементы из массива и добавить новый элемент, равный сумме удаленных элементов ( arr [i] + arr [j] ), с ключом, равным ключу большего элемента среди arr[i] и arr[j]. Если оба элемента равны, то можно использовать любой ключ из двух. Задача состоит в том, чтобы вывести в конце все возможные уникальные ключи, когда массив содержит только один элемент.

Примеры:

Input: N = 3, arr[] = {2, 3, 4}
Output: 1, 2
Explanation: Initially all elements have keys equal to their index. (2->0, 3->1, 4->2).
Case 1:

  • Remove 2 and 3 and insert 5 with key 1. The new array will be (5->1, 4->2)
  • Remove 5 and 4 and insert 9 with key 1. The new array will be (9->1)
  • The final index in the array will be 1 for these operations.

Case 2:

  • Remove 2 and 4 and insert 6 with key 2. The new array will be (3->1, 6->2)
  • Remove 6 and 3 and insert 9 with key 2. The new array will be (9->2)
  • The final index in the array will be 2 for these operations.

So there are a total of 2 possible unique keys (1 and 2).

 

Input: N = 3, arr[] = {1, 1, 4}
Output: 2 
Explanation: The final index left will be 2 in all cases. So there is a total of 1 possible index.

 

Подход: поддерживайте вектор пар, который будет быть хранение {value, i} для каждого arr[i] и переменной sum, в которой будет храниться оставшаяся сумма левой части. Сортируем вектор в порядке неубывания ценность а также начать обход с конца. Всякий раз, когда оставшаяся сумма левой части массив меньше, чем значение текущего элемента, что означает, что все элементы в левой части никогда не могут быть ответом, поэтому мы прерываем цикл отсюда, потому что эти элементы в левой части будут в конце заменены ключами более крупные элементы справа.

Следуйте приведенным ниже шагам в качестве алгоритма для описанного выше подхода:

  • Поддерживайте парный вектор, который хранит элементы массива в виде {значение, индекс}
  • Отсортируйте парный вектор в порядке неубывания значения.
  • Возьмите переменную sum , которая изначально будет хранить сумму всех элементов массива.
  • Итерация справа налево в отсортированном векторе.
  • Если значение текущего элемента больше, чем сумма всех элементов в его левой части, тогда разорвите цикл, в противном случае добавьте текущий индекс в качестве действительного ответа и уменьшите сумму на значение текущего элемента и продолжите для оставшихся элементов .
  • В конце верните все возможные индексы в ответ.

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


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

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