Распечатайте лексикографически наименьший массив, уменьшив K до 0 за минимальное количество операций.

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

Дан массив arr[] и целое число K. Задача состоит в том, чтобы уменьшить значение K до 0 , выполнив следующие операции. Одна операция определяется как выбор 2 индексов i, j и вычитание минимума arr[i] и K (т. е. X = min(arr[i], K) из arr[i] (т. е. arr[i] = arr [i] – X) и прибавив к arr[j] минимальное значение (arr[j] = arr[j] + X) и выведите лексикографически наименьший массив. Обратите внимание, что элементы массива arr[] не могут быть отрицательными .

Примеры:

Input: N = 4, K = 2, arr[] = {4, 3, 2, 1}  
Output: 2 2 3 3 
Explanation: 
Operation 1: Select indices 0 and 3, then subtract min of arr[0](=4) and K(=2) from arr[0] and add the minimum value i.e K(=2) in arr[3](=1). Now, the modified array is {2, 3, 2, 3}
Now, sort the modified array and print it.

Input: N = 3, K = 15, arr[] = {1, 2, 3}  
Output: 0 0 6
Explanation: 
Operation 1: Select indices 0 and 2, then subtract min of arr[0](=1) and K(=15) from arr[0] and add the minimum value i.e arr[0](=1) in arr[2](=3). Now the modified array is {0, 2, 4}.
Operation 2: Select indices 1 and 2, then subtract min of arr[1](=2) and K(=15) from arr[1] and add the minimum value i.e arr[1](=2) in arr[2](=4). Now the modified array is {0, 0, 6}.
Now, sort the modified array and print it.

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

  • Переберите диапазон [0, N-1], используя переменную i , и выполните следующие шаги:
    • Если arr[i] меньше K, выполните следующие действия.
    • Вычтите arr[i] из переменной K, добавьте значение arr[i] к arr[n-1] и установите значение arr[i] равным 0.
    • В противном случае вычтите K из значения arr[i], добавьте значение K к arr[n-1] и установите значение K равным 0 и разорвите цикл.
  • Отсортируйте массив arr[] .
  • После выполнения вышеуказанных действий выведите элементы массива arr[] .

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

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

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