Минимизируйте операции, чтобы сделать все элементы массива -1, изменив максимумы подмассива размера K на -1.

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

Для данного массива arr[] , состоящего из N целых чисел и целого числа K , задача состоит в том, чтобы найти минимум операций, необходимых для того, чтобы сделать все элементы массива равными -1 , чтобы в каждой операции выбирать подмассив размера K и изменять все максимальные элемент в подмассиве до -1 .

Примеры:

Input: arr[] = {18, 11, 18, 11, 18}, K = 3 
Output: 3
Explanation:
Following are the operations performed:

  1. Choosing the sub array from index 0 to 2 and by applying the operation, modifies the array to {-1, 11, -1, 11, 18}.
  2. Choosing the sub array form index 1 to 3 and by applying the operation, modifies the array to {-1, -1, -1, -1, 18}.
  3. Choosing the sub array form index 2 to 4 and by applying the operation, modifies the array to {-1, -1, -1, -1, -1}.

After the above operations all the array elements become -1. Therefore, the minimum number of operations required is 3.

Input: arr[] = {2, 1, 1}, K = 2
Output: 2

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

  • Инициализируйте вектор пар, скажем, vp[] , который хранит элементы массива с их индексами.
  • Инициализируйте переменную, скажем, minCnt как 0 , которая хранит счетчик минимального количества операций.
  • Пройдите массив arr[] и поместите arr[i] вместе с его индексом i в вектор vp .
  • Отсортируйте вектор пар vp[] по первому значению.
  • Проходим по вектору vp[] до тех пор, пока он не станет пустым, и выполняем следующие шаги:
    • Увеличьте значение minCnt на 1 .
    • Извлеките все элементы из вектора vp[] сзади, имеющие одинаковое значение (первый элемент каждой пары) и имеющие различия между индексами меньше, чем K .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение minCnt .

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

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

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